Submission #1130132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130132		gyg	Mensza (COI22_mensza)	C++20	100 / 100	2229 ms	76508 KiB

Main

/*
For the last subtask, it's infeasible to communicate A and B exactly. 

Notice that A > B iff there is some same length prefix which is identical except for the last bit (which is 1 in A and
0 in B).

For every prefix of A ending in 1 (e.g. 0110101...) we can output it as a number (pad the right with 0s). 
We want the same prefix of B to collide iff it's the same except for the last bit. So, for every prefix of B ending
in 0, output it similarly but convert the last bit to 1.
*/

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define str string
#define vec vector

bool on(int x, int i) { return x & (1 << i); }
int prf(int x, int i) {
    int ans = 0;
    for (int j = 20; j >= i; j--)
        if (on(x, j)) ans += 1ll << j;
    return ans;
}

void slv(int tst) {
    str typ; cin >> typ;
    if (typ[0] == 'a') {
        int x; cin >> x;
        vec<int> ans;
        for (int i = 20; i >= 0; i--) {
            if (!on(x, i)) continue;
            ans.push_back(prf(x, i));
        }
        cout << ans.size() << " ";
        for (int y : ans) cout << y << " ";
        cout << endl;
    } if (typ[0] == 'b') {
        int x; cin >> x;
        vec<int> ans;
        for (int i = 20; i >= 0; i--) {
            if (on(x, i)) continue;
            ans.push_back(prf(x ^ (1ll << i), i));
        }
        cout << ans.size() << " ";
        for (int y : ans) cout << y << " ";
        cout << endl;
    } if (typ[0] == 'c') {
        int sz; cin >> sz;
        vec<int> vl;
        for (int i = 1; i <= sz; i++) {
            int x; cin >> x;
            vl.push_back(x);
        }
        bool ans = (*max_element(vl.begin(), vl.end()) == 2);
        cout << (ans ? "A" : "B") << endl;
    }
}

signed main() {
    // freopen("a.in", "r", stdin);
    cin.sync_with_stdio(false), cin.tie(0);
    int l, q; cin >> l >> q;
    for (int i = 1; i <= q; i++) slv(i);
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66