QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#297987#7863. Parity Gameucup-team902#TL 0ms0kbC++175.0kb2024-01-05 15:21:462024-01-05 15:21:48

Judging History

你现在查看的是最新测评结果

  • [2024-01-05 15:21:48]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-01-05 15:21:46]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

const int N = 505;

int n, t;
int a[N];

int winning[2] = {0, 1};
string name[2] = {"Alice", "Bob"};

inline void maintain(int x, int op){
    a[x] = (op ? (a[x] ^ a[x + 1]) : (a[x] & a[x + 1]));
    for(int i = x + 1; i < n; ++i){
        a[i] = a[i + 1];
    }
    --n;
}

inline void answer(int x, int op, bool ot = 1){
    if(ot){
        cout << x << ' ' << (op ? '+' : '*') << endl;
        fflush(stdout);
    }
    maintain(x, op);
}

inline void read(){
    int y; cin >> y;
    char c; cin >> c;
    while(c == ' ') cin >> c;
    maintain(y, c == '+');
    // int y = rand() % (n - 1) + 1, op = rand() % 2;
    // cerr << y << " " << (op ? '+' : '*') << endl;
    // maintain(y, op);
}

inline bool strategy1(int ot = 1){
    if(a[1] == 1 && a[2] == 1){
        answer(1, 1, ot);
    }
    else {
        answer(1, 0, ot);
    }
    return true;
}

inline bool checkstate(bool isfirst){
    int cnt = 0;
    for(int i = 1; i <= n; ++i){
        if(a[i] == 1){
            int j = i;
            while(j < n && a[j + 1] == 1) ++j;
            if((j - i + 1) % 2 == 1){
                ++cnt;
            }
            i = j;
        }
        else --cnt;
    }
    return cnt + isfirst > 0;
}

inline bool strategy2(int ot = 1){
    for(int i = 1; i < n; ++i){
        vector<int> a_ = vector<int>(a + 1, a + n + 1);
        answer(i, 1, 0);
        bool ok = checkstate(0);
        ++n;
        for(int j = 1; j <= n; ++j) a[j] = a_[j - 1];
        if(ok){
            answer(i, 1, ot);
            return 1;
        }
        answer(i, 0, 0);
        ok = checkstate(0);
        ++n;
        for(int j = 1; j <= n; ++j) a[j] = a_[j - 1];
        if(ok){
            answer(i, 0, ot);
            return 1;
        }
    }
    answer(1, 1, ot);
    return 0;
}

inline bool strategy3(int ot = 1){
    for(int i = 1; i < n; ++i){
        vector<int> a_ = vector<int>(a + 1, a + n + 1);
        answer(i, 1, 0);
        bool ok = !checkstate(1);
        ++n;
        for(int j = 1; j <= n; ++j) a[j] = a_[j - 1];
        if(ok){
            answer(i, 1, ot);
            return 1;
        }
        answer(i, 0, 0);
        ok = !checkstate(1);
        ++n;
        for(int j = 1; j <= n; ++j) a[j] = a_[j - 1];
        if(ok){
            answer(i, 0, ot);
            return 1;
        }
    }
    answer(1, 1, ot);
    return 0;
}

inline void work1(int me){
    cout << name[me] << endl;
    fflush(stdout);
    int player = 0;
    while(n != 1){
        if(player == me){
            strategy1();
        }
        else{
            read();
        }
        player ^= 1;
    }
    // assert(a[1] == winning[me]);
}

inline void work2(int me){
    // cerr << "work2" << endl;
    cout << name[me] << endl;
    fflush(stdout);
    int player = 0;
    while(n != 1){
        // cout << name[player] << endl;
        if(player == me){
            strategy2();
        }
        else{
            read();
            // strategy3();
        }
        player ^= 1;
        // cerr << n << ": ";
        // for(int i = 1; i <= n; ++i) cerr << a[i] << ' '; cerr << endl;
    }
    assert(a[1] == winning[me]);
}

inline void work3(int me){
    // cerr << "work3" << endl;
    cout << name[me] << endl;
    fflush(stdout);
    int player = 0;
    while(n != 1){
        if(player == me){
            strategy3();
        }
        else{
            read();
            // strategy2();
        }
        player ^= 1;
    }
    // cerr << "test" << endl;
    while(a[1] != winning[me]);
}

bool check(int me){
    int n_ = n;
    vector<int> a_ = vector<int>(a + 1, a + n + 1);

    int player = 0;
    while(n != 1){
        if(player == me){
            strategy2(1);
        }
        else{
            strategy3(1);
        }
        player ^= 1;
    }

    bool res = (a[1] == winning[me]);
    n = n_;
    for(int i = 1; i <= n; ++i){
        a[i] = a_[i - 1];
    }
    // cerr << "check: " << res << endl;
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    auto seed = time(0);
    srand(seed);
    // cerr << seed << endl;
    while(1){
        // cerr << seed << endl;
        // n = rand() % 6 + 2;
        // t = rand() % 2;
        // for(int i = 1; i <= n; ++i){
        //     a[i] = rand() % 2;
        // }
        // cerr << n << " " << t << endl;
        // for(int i = 1; i <= n; ++i){
        //     cerr << a[i] << " ";
        // }
        // cerr << endl;
        cin >> n >> t;
        for(int i = 1; i <= n; ++i){
            cin >> a[i];
        }
        int lstplayer = n & 1;
        winning[0] ^= t;
        winning[1] ^= t;
        if(winning[lstplayer] == 0){
            work1(lstplayer);
        }
        else{
            if(checkstate(lstplayer == 0)){
                work2(lstplayer);
            }
            else{
                work3(lstplayer ^ 1);
            }
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

4 1
0 1 0 1
1 *
1

output:

Alice
1 +
1 +

result: