QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#297987 | #7863. Parity Game | ucup-team902# | TL | 0ms | 0kb | C++17 | 5.0kb | 2024-01-05 15:21:46 | 2024-01-05 15:21:48 |
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 +