Submission #1166998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166998		Sang	Message (IOI24_message)	C++20	100 / 100	397 ms	848 KiB

message

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

#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task ".\\IOI24_P2\\2-04"

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;

const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 2277;

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 (i, 0, 30){
        if (C[i]) continue;
        if (last != -1){
            d[last] = i - last;
            s += i - last;
        }
        last = i;
    }
    FOR (i, 0, 30){
        if (C[i] == 0){
            d[last] = i + 31 - last;
            s += i + 31 - last;
            break;
        }
    }
    assert(s == 31);
    last = M.back();
    FOR (i, 1, 66){
        vector<bool> packet;
        FOR (j, 0, 30){
            if (C[j] || d[j] > i) {
                packet.pb(0);
                continue;
            }
            if (d[j] == i){
                packet.pb(1);
                continue;
            }
            packet.pb((!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 (i, 0, 16){
        FOR (j, 0, 30){
            if (d[j] || R[i][j] == 0)  continue;
            d[j] = i + 1;
        }
    }
    vector<int> good(35, 0);
    FOR (i, 0, 30){
        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 (i, 0, 65){
        FOR (j, 0, 30){
            if (!good[j]) continue;
            if (i + 1 <= d[j]) continue;
            ans.pb(R[i][j]);
         }
    }

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

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

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".in", "r")){
        freopen(task".in", "r", stdin);
    }
    int t; cin >> t;
    FOR (i, 1, t){
        int S; cin >> S;
        vector<bool> M(S), C(31);
        FOR (i, 0, S - 1){
            int x; cin >> x;
            M[i] = x;
        }
        FOR (i, 0, 30) {
            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_

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