Submission #1175872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175872		_8_8_	Message (IOI24_message)	C++20	0 / 100	323 ms	1048 KiB

message

#include "message.h"
#include <bits/stdc++.h>

using namespace std;
const int N = 1024, B = 31, F = 16, Q = 66;

mt19937 rng(123321);
void send_message(vector<bool> a, vector<bool> c) {
    vector<int> mem, d(F);
    for(int i = 0; i < B; i++) {
        if(!c[i]) {
            mem.push_back(i);
        }
    }
    for(int i = 0; i < F; ++i) {
        d[i] = (mem[(i + 1) % F] - mem[i] + B) % B  - 1;
    }
    vector<bool> s(B);
    int it = 0, n = (int)a.size();
    for(int i = 0; i < Q; i++) {
        for(int j = 0; j < F; j++) {
            if(d[j] >= i) {
                s[mem[j]] = 0;
                if(d[j] == i) {
                    s[mem[j]] = 1;
                }
            } else {
                if(it < n) {
                    s[mem[j]] = a[it++];
                }
            }
        }
        send_packet(s);
    }
    for(int i = 0; i < F; i++) {
        if((n >> i) & 1) {
            s[mem[i]] = 1;
        } else {
            s[mem[i]] = 0;
        }
    }
    send_packet(s);
}
vector<int> g[N];
int m, pr[N][B], nx[N];
bool dp[N][B];
bool vis[N];

vector<int> get() {
    for(int i = 0; i < B; i++) dp[i][1] = 1;
    memset(pr, -1, sizeof(pr));
    for(int i = B - 1; i >= 0; i--) {
        for(int j = 2; j <= F; j++) {
            for(int to : g[i]) {
                if(to <= i) continue;
                if(dp[to][j - 1]) {
                    dp[i][j] = 1;
                    pr[i][j] = to;
                }
            }
        }
    }
    vector<int> ret;
    for(int i = 0; i < B; i++) {
        if(dp[i][F]) {
            vector<int> r(1, i);
            int x = i, it = F;
            while(it > 1) {
                x = pr[x][it];
                r.push_back(x);
                it--;
            }
            if(nx[r.back()] == i) {
                // assert((int)ret.empty());
                ret = r;
            }
        }
    }
    // assert((int)ret.size() == F);
    return ret;
}
vector<bool> receive_message(vector<vector<bool>> R) {
    vector<bool> res;
    vector<bool> len = R.back();R.pop_back();
    int sz = 0;
    m = (int)R.size();
    for(int i = 0; i < B; i++) nx[i] = -1;
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < B; j++) {
            if(vis[j]) continue;
            if(R[i][j] == 1) {
                g[j].push_back((j + i + 1) % B);
                nx[j] = (j + i + 1) % B;
                vis[j] = 1;
            }
        }
    }
    vector<int> mem = get(), d(F);
    return res;
    for(int j = 0; j < F; j++) {
        if(len[mem[j]]) {
            sz += (1 << j);
        }
    }
    for(int i = 0; i < F; ++i) {
        d[i] = (mem[(i + 1) % F] - mem[i] + B) % B  - 1;
    }
    for(int i = 0; i < Q; i++) {
        for(int j = 0; j < F; j++) {
            if(d[j] >= i) {

            } else {
                if((int)res.size() < sz) res.push_back(R[i][mem[j]]);
            }
        }
    }    
    return res;
}

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