結果

問題 No.1149 色塗りゲーム
ユーザー tkmst201
提出日時 2021-01-20 15:49:34
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,047 bytes
コンパイル時間 1,914 ms
コンパイル使用メモリ 206,548 KB
最終ジャッジ日時 2025-01-18 02:51:19
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 13 WA * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) begin(v),end(v)
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = false;
//---------------------------------//
int main() {
    int N;
    cin >> N;
    vector<int> grundy(N + 1);
    grundy[0] = 0;
    
    vector<bool> done;
    FOR(i, 1, N + 1) {
        done.assign(N + 1, false);
        REP(j, i) {
            done[grundy[j] ^ grundy[i - 1 - j]] = true;
            if (j + 1 < i) done[grundy[j] ^ grundy[i - 2 - j]] = true;
        }
        REP(j, i + 1) if (!done[j]) { grundy[i] = j; break; }
    }
    
    auto query = [](vector<bool> & board, int k, int x) -> pii {
        board[x] = true;
        if (k == 2) board[x + 1] = true;
        cout << k << " " << x + 1 << endl;
        int t;
        cin >> t;
        if (t <= 1) return {-1, 0};
        cin >> k >> x; --x;
        if (t == 2) return {-1, 0};
        board[x] = true;
        if (k == 2) board[x + 1] = true;
        return {k, x};
    };
    
    vector<bool> board(N);
    while (true) {
        vector<pii> cnt; // cnt, pos
        for (int i = 0, r = 0; i < N; i = r) {
            while (r < N && !board[r]) ++r;
            if (i == r) ++r;
            else cnt.emplace_back(r - i, i);
        }
        int g = 0;
        for (auto [c, _] : cnt) g ^= grundy[c];
        
        assert(g > 0);
        
        int mxbit = -1;
        for (int i = 6; i >= 0; --i) if (g >> i & 1) { mxbit = i; break; }
        
        pii cur {-1, 0};
        for (auto [c, p] : cnt) {
            if (~c >> mxbit & 1) continue;
            int nex = grundy[c] ^ g;
            REP(i, c) {
                if ((grundy[i] ^ grundy[c - 1 - i]) == nex) { cur = {1, p + i}; break; }
                if (i + 1 < c && (grundy[i] ^ grundy[c - 2 - i]) == nex) { cur = {2, p + i}; break; }
            }
            break;
        }
        
        auto res = query(board, cur.first, cur.second);
        if (res.first == -1) break;
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0