QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#548342#8311. Game on Sequencehaze#WA 0ms3604kbC++232.6kb2024-09-05 17:20:092024-09-05 17:20:09

Judging History

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

  • [2024-09-05 17:20:09]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3604kb
  • [2024-09-05 17:20:09]
  • 提交

answer

/*

Author: Haze

2024/9/5

*/

#include <bits/stdc++.h>

#define irep(i, l, r) for(int i = (l); i <= (r); ++ i)
#define drep(i, r, l) for(int i = (r); i >= (l); -- i)
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr);
using namespace std;
typedef long long ll;

inline ll readL() {
    ll s = 0;
    bool fl = false;
    char ch = (char) getchar();
    while (!isdigit(ch)) {
        if (ch == '-')fl = true;
        ch = (char) getchar();
    }
    while (isdigit(ch)) {
        s = s * 10 + (ch ^ 48);
        ch = (char) getchar();
    }
    return fl ? -s : s;
}

inline int read() {
    return (int) (readL());
}

const int mod = 1000000000 + 7;
const int itinf = 1000000999;
const ll llinf = 2e18;
const int N = 500099;

int popcount(int x){
    if(x)return 1 + popcount(x - (x & -x));
    return 0;
}

void solve() {
    int n = read(), m = read();
    vector<array<int, 2>>qr;
    vector<int>pos[256], t;
    irep(i, 0, n - 1){
        int x = read();
        pos[x].push_back(i);
        t.push_back(x);
    }
    irep(isd, 0, m - 1){
        int op = read();
        if(op == 1){
            int k = read();
            pos[k].push_back(n ++);
            t.push_back(k);
        }
        else{
            int p = read() - 1, v = t[p], L = 0;
            vector<array<int, 2>>a;
            irep(i, 0, 255){
                auto it = upper_bound(pos[i].begin(), pos[i].end(), p);
                if(it != pos[i].end())a.push_back({*it, i});
            }
            sort(a.begin(), a.end());
            vector<int>usd(256);
            vector<int>wl(256);
//            for(auto [pp, ppp] : a)cerr << ppp << ' ';
//            cerr << endl;
            drep(i, a.size() - 1, 0){
                int val = a[i][1], ok = 0, flag = 0;
                for(int b = 1; b < 256; b <<= 1){
                    if(usd[b ^ val]){
                        ok = 1;
                        if(wl[b ^ val] == 0){
                            flag = 1;
                            break;
                        }
                    }
                }
                if(flag)wl[val] = 1;
                else wl[val] = 0;
                usd[val] = 1;
//                cerr << v << ' ' << val << ' ' << wl[val] << endl;
                if(popcount(val ^ v) <= 1 && wl[val] == 0){
                    L = 1;
                    break;
                }
            }
            cout << (L ? "Grammy" : "Alice") << '\n';
        }
    }
}

int main() {
    // IOS
    int T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3600kb

input:

5 5
1 2 3 4 5
1 6
2 5
1 7
2 5
2 1

output:

Alice
Grammy
Alice

result:

ok 3 lines

Test #2:

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

input:

10 10
12 114 132 7 133 53 128 159 34 92
2 5
1 254
2 3
2 11
1 92
2 11
1 33
1 230
1 181
2 11

output:

Alice
Grammy
Alice
Alice
Alice

result:

ok 5 lines

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3548kb

input:

100 100
57 58 24 217 80 0 241 175 19 138 231 17 8 19 22 100 133 205 178 67 55 92 127 254 156 89 87 22 136 208 168 195 164 194 243 110 234 164 78 55 43 223 227 112 137 78 111 31 253 194 196 128 210 129 71 129 40 195 114 69 114 52 83 162 248 117 12 162 86 155 81 6 251 174 237 190 171 44 61 114 254 131...

output:

Grammy
Grammy
Alice
Alice
Grammy
Grammy
Alice
Alice
Grammy
Alice
Grammy
Grammy
Grammy
Grammy
Grammy
Alice
Alice
Alice
Alice
Grammy
Alice
Grammy
Alice
Grammy
Alice
Grammy
Grammy
Alice
Grammy
Grammy
Alice
Alice
Grammy
Grammy
Grammy
Alice
Alice
Grammy
Alice
Grammy
Grammy
Grammy
Grammy
Alice
Grammy
Grammy

result:

wrong answer 14th lines differ - expected: 'Alice', found: 'Grammy'