WARush

SRMの結果とか、解けた問題のコードを書いていきます

AtCoder Regular Contest #013 C "笑いをとれるかな?"

考えた事

うわ~3次元だよ・・
豆腐も複数、ハバネロも複数
どうしていいのかわからない。
点対称にするかどうかの勝負なのか?

とりあえず2次元から図を書いてみよう。
どうもハバネロというのは切れるところを制限するものだな。

軸を1つだけにして考えよう。
たとえば幅が5つあってハバネロがインデックス1にあれば、
切れる場所は1+3になる。
インデックス4にもあれば、
切れる場所は1+1になる。
切れる場所がなくなった人の負け。

要はNimだ。
切ったときにX.Y.Z軸で互いに影響はないから、
各軸で切れるところが何箇所あるかだして、
それをxorしてけばいい。

ソースコード
int main() {
    istream& in = cin;
    int n;
    in >> n;
    int xr = 0; // xor これが0だったら先行の負け
    int INF = INT_MAX;
    for( int i = 0; i < n; i++ ){
        int X, Y, Z;
        in >> X >> Y >> Z;
        int m;
        in >> m;
        int minX, minY, minZ, maxX, maxY, maxZ;
        minX = minY = minZ = INF;
        maxX = maxY = maxZ = 0;
        for( int j = 0; j < m; j++ ){
            int x, y, z;
            in >> x >> y >> z;
            // それぞれの軸でハバネロの位置の最小と最大を出す
            minX = min( minX, x ); minY = min( minY, y ); minZ = min( minZ, z ); 
            maxX = max( maxX, x ); maxY = max( maxY, y ); maxZ = max( maxZ, z );
        }
        // 切れる箇所をxorしてく
        xr ^=minX; xr ^= minY; xr ^= minZ;
        xr ^= X - maxX - 1; xr ^= Y - maxY - 1; xr ^= Z - maxZ - 1;
    }

    cout << (xr != 0 ? "WIN" : "LOSE") << endl;
}