QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#289406#7863. Parity Gameucup-team1055#TL 1ms3848kbC++204.0kb2023-12-23 17:31:272023-12-23 17:31:27

Judging History

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

  • [2023-12-23 17:31:27]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3848kb
  • [2023-12-23 17:31:27]
  • 提交

answer

#include <bits/stdc++.h>

#define rep(i,s,n) for(int i = int(s); i < int(n); i++)
#define rrep(i,s,n) for(int i = int(n) - 1; i >= int(s); i--)
#define all(v) (v).begin(), (v).end()

using ll = long long;
using ull = unsigned long long;
using ld = long double;

template<class T>
bool chmin(T &a, T b) {
    if(a <= b) return false;
    a = b;
    return true;
}

template<class T>
bool chmax(T &a, T b) {
    if(a >= b) return false;
    a = b;
    return true;
}

using namespace std;

vector<int> process(vector<int> v, int i, char c){
    int x = v[i];
    int y = v[i+1];
    int z = (c == '+' ? (x^y) : (x&y));
    v.erase(v.begin()+i,v.begin()+i+2);
    v.insert(v.begin()+i,z);
    return v;
}

char which(int x, int y, int z){
    if (z == 0){
        if (x == 0 || y == 0) return '*';
        else return '+';
    }
    else {
        assert(x != 0 || y != 0);
        if (x == 0 || y == 0) return '+';
        else return '*';
    }
}

bool is_lose_pattern(vector<int> a){
    int n = a.size();
    assert(n % 2 == 1);
    rep(i,0,n){
        if (i % 2 == 0 && a[i] != 1){
            return false;
        }
    }
    return true;
}

pair<int,char> can_move_to_lose(vector<int> a){
    int n = a.size();
    int p = -1;
    char c = '?';
    rep(i,0,n-1){
        auto na = process(a,i,'+');
        if (is_lose_pattern(na)){
            p = i, c = '+';
        }
        auto ma = process(a,i,'*');
        if (is_lose_pattern(ma)){
            p = i, c = '*';
        }
    }
    return make_pair(p,c);
}

pair<int,char> strategy(vector<int> a){
    int n = a.size();
    int p = -1;
    char c = '?';
    rep(i,0,n-1){
        auto na = process(a,i,'+');
        if (can_move_to_lose(na).first == -1){
            p = i, c = '+';
        }
        auto ma = process(a,i,'*');
        if (can_move_to_lose(ma).first == -1){
            p = i, c = '*';
        }
    }
    return make_pair(p,c);
}

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int n, t; cin >> n >> t;
    vector<int> a(n);
    rep(i,0,n) cin >> a[i];
    auto ask = [&](int p, char c){
        cout << p+1 << ' ' << c << endl;
        a = process(a,p,c);
        n--;
    };
    auto hear = [&](){
        int p; cin >> p; p--;
        char c; cin >> c;
        a = process(a,p,c);
        n--;
    };
    if (n % 2 == 0 && t == 0){
        cout << "Alice" << endl;
        while (n > 2){
            ask(0,'+');
            hear();
        }
        ask(0,which(a[0],a[1],0));
        return 0;
    }
    if (n % 2 == 1 && t == 1){
        cout << "Bob" << endl;
        hear();
        while (n > 2){
            ask(0,'+');
            hear();
        }
        ask(0,which(a[0],a[1],0));
        return 0;
    }
    if (n % 2 == 1){
        if (is_lose_pattern(a)){
            cout << "Bob" << endl;
            while (n > 1){
                hear();
                auto [p, c] = can_move_to_lose(a);
                assert(p != -1);
                ask(p,c);
            }
            return 0;
        }
        else {
            cout << "Alice" << endl;
            while (n > 1){
                auto [p, c] = strategy(a);
                assert(p != -1);
                ask(p,c);
                hear();
            }
            return 0;
        }
    }
    else {
        auto [ip, ic] = can_move_to_lose(a);
        if (ip != -1){
            cout << "Alice" << endl;
            ask(ip,ic);
            while (n > 1){
                hear();
                auto [p, c] = can_move_to_lose(a);
                assert(p != -1);
                ask(p,c);
            }
            return 0;
        }
        else {
            cout << "Bob" << endl;
            hear();
            while (n > 1){
                auto [p, c] = strategy(a);
                assert(p != -1);
                ask(p,c);
                hear();
            }
            return 0;
        }
    }
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3512kb

input:

4 1
0 1 0 1
1 *
1

output:

Alice
1 +
1 +

result:

ok The player wins!

Test #2:

score: 0
Accepted
time: 1ms
memory: 3848kb

input:

4 0
1 0 1 0
1 *
1

output:

Alice
1 +
1 *

result:

ok The player wins!

Test #3:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

5 1
1 1 1 0 0
4 +
1 +
1

output:

Bob
1 +
1 *

result:

ok The player wins!

Test #4:

score: 0
Accepted
time: 1ms
memory: 3596kb

input:

3 0
1 1 1
1 +
1

output:

Bob
1 +

result:

ok The player wins!

Test #5:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

3 1
1 0 1
1 *
1

output:

Bob
1 *

result:

ok The player wins!

Test #6:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

3 0
1 0 1
1 *
1

output:

Bob
1 +

result:

ok The player wins!

Test #7:

score: 0
Accepted
time: 1ms
memory: 3604kb

input:

2 1
0 1
1

output:

Alice
1 +

result:

ok The player wins!

Test #8:

score: -100
Time Limit Exceeded

input:

499 0
0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 0 ...

output:

Alice
498 *
496 *
493 +
491 *
489 +
487 *
485 *
483 +
481 +
479 *
477 +
475 *
473 +
471 *
469 +
467 +
465 *
463 *
461 +
459 +
457 *
455 +
453 *
451 +
449 +
447 +
445 *
443 +
441 *
439 *
437 +
435 +
433 +
431 +
429 *
427 +
425 +
423 *
421 *
419 +
417 *
415 +
413 +
411 *
409 +
407 +
405 *
403 +
401 +
...

result: