Submission #1175877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175877		_8_8_	Message (IOI24_message)	C++20	100 / 100	402 ms	1072 KiB

message

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

using namespace std;
const int N = 1024, B = 31, F = 16, Q = 66;
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();
    int w = (1024 - n);
    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(w >= 0) {
                    if(!w) {
                        s[mem[j]] = 1;
                    } else {
                        s[mem[j]] = 0;
                    }
                    w--;
                } else {
                    if(it < n) {
                        s[mem[j]] = a[it++];
                    }   
                }
            }
        }
        send_packet(s);
    }
}
vector<int> g[N];
int m, pr[N][B], nx[N];
bool dp[N][B];
bool vis[N];

vector<int> get() {
    memset(dp, 0, sizeof(dp));
    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;
    int sz = 0;
    m = (int)R.size();
    for(int i = 0; i < B; i++) nx[i] = -1;
    for(int j =0 ; j < B; j++) g[j].clear(), vis[j] = 0;
    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);
    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) {
                res.push_back(R[i][mem[j]]);
            }
        }
    }    
    reverse(res.begin(), res.end());
    while(!res.empty() && !res.back()) res.pop_back();
    res.pop_back();
    reverse(res.begin(), res.end());
    return res;
}

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