Submission #1172132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172132		sagnbaevv	Message (IOI24_message)	C++20	100 / 100	403 ms	848 KiB

message

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 100005;
const int INF = 0x3f3f3f3f;
const int MOD = 10000002277;

vector<bool> send_packet(vector<bool> A);

void send_message(vector<bool> M, vector<bool> C) {
    vector<int> d(35, 0);
    int last = -1;
    int s = 0;
    for (int i = 0; i <= 30; i++) {
        if (C[i]) continue;
        if (last != -1) {
            d[last] = i - last;
            s += i - last;
        }
        last = i;
    }
    for (int i = 0; i <= 30; i++) {
        if (C[i] == 0) {
            d[last] = i + 31 - last;
            s += i + 31 - last;
            break;
        }
    }
    assert(s == 31);
    last = M.back();
    for (int i = 1; i <= 66; i++) {
        vector<bool> packet;
        for (int j = 0; j <= 30; j++) {
            if (C[j] || d[j] > i) {
                packet.push_back(0);
                continue;
            }
            if (d[j] == i) {
                packet.push_back(1);
                continue;
            }
            packet.push_back((!M.empty() ? M.back() : (last ^ 1)));
            if (!M.empty()) {
                last = M.back();
                M.pop_back();
            }
        }
        send_packet(packet);
    }
}

vector<bool> receive_message(vector<vector<bool>> R) {
    vector<int> d(35, 0);
    for (int i = 0; i <= 16; i++) {
        for (int j = 0; j <= 30; j++) {
            if (d[j] || R[i][j] == 0) continue;
            d[j] = i + 1;
        }
    }
    vector<int> good(35, 0);
    for (int i = 0; i <= 30; i++) {
        int j = i;
        int cnt = 1;
        while (d[j] && j + d[j] <= 30) {
            ++cnt;
            j += d[j];
        }
        if (cnt != 16 || (j + d[j]) % 31 != i) {
            continue;
        }
        j = i;
        while (d[j] && j + d[j] <= 30) {
            good[j] = 1;
            j += d[j];
        }
        good[j] = 1;
        break;
    }
    vector<bool> ans;
    for (int i = 0; i <= 65; i++) {
        for (int j = 0; j <= 30; j++) {
            if (!good[j]) continue;
            if (i + 1 <= d[j]) continue;
            ans.push_back(R[i][j]);
        }
    }

    int last = ans.back();
    while (!ans.empty() && ans.back() == last) ans.pop_back();
    reverse(ans.begin(), ans.end());
    return ans;
}

#ifdef _Pbrngw_
vector<vector<bool>> R;
vector<bool> send_packet(vector<bool> A) {
    assert(A.size() == 31);
    R.push_back(A);
    return A;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); 
    cout.tie(0);
    if (fopen(".\\IOI24_P2\\2-04.in", "r")) {
        freopen(".\\IOI24_P2\\2-04.in", "r", stdin);
    }
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        int S;
        cin >> S;
        vector<bool> M(S), C(31);
        for (int i = 0; i < S; i++) {
            int x;
            cin >> x;
            M[i] = x;
        }
        for (int i = 0; i <= 30; i++) {
            int x;
            cin >> x;
            C[i] = x;
        }
        R.clear();
        send_message(M, C);
        vector<bool> ans = receive_message(R);
        if (ans != M) {
            cout << i << '\n';
            return 0;
        }
        cout << "AC\n";
    }

    return 0;
}
#endif // _Pbrngw_

Compilation message (stderr)

message.cpp:6:17: warning: overflow in conversion from 'long int' to 'int' changes value from '10000002277' to '1410067685' [-Woverflow]
    6 | const int MOD = 10000002277;
      |                 ^~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 90 / 90