Submission #1242163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242163		dosts	Message (IOI24_message)	C++20	10 / 100	381 ms	848 KiB

message

#include "message.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int pack = 66;
void send_message(std::vector<bool> M, std::vector<bool> C) {
    bool anti = !M.back();
    while (M.size() != pack*16-31) M.push_back(anti);
    const int n = 31;
    int ptr = 0;
    int S = big(M);
    int round = 0;
    vi done(n,0),nxt(n,0);
    for (int i = 0;i<n;i++) {
        if (C[i]) continue;
        int j = i+1;
        while (C[j%n]) {
            j++;
        }
        nxt[i] = (j-i+n)%n;
    }
    vector<bool> cur(n,0);
    while (ptr < S) {
        ++round;
        for (int j = 0;j<n && ptr < S;j++) {
            if (C[j]) continue;
            if (done[j]) {
                cur[j] = M[ptr++];
            }
            else {
                if (round == nxt[j]) {
                    done[j] = 1;
                    cur[j] = 1;
                }
                else {
                    cur[j] = 0;
                }
            }
        }
        send_packet(cur);
    }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
    const int n = 31;
    vi f(n,-1);
    int packet = 0;
    int readd = 0;
    while (readd < n && packet<=16 && packet < pack) {
        for (int j = 0;j<n;j++) {
            if (f[j] != -1) continue;
            if (R[packet][j] == 1) {
                f[j] = packet+1;
                readd++;
            }
        }
        packet++;
    }
    vi secure;
    for (int i = 0;i<n;i++) {
        vi lmao;
        lmao.push_back(i);
        int j = (i+f[i])%n;
        while (j != i && lmao.size() < 16) {
            lmao.push_back(j);
            j = (j+f[j])%n;
        }
        if (lmao.size() != 16) continue;
        if (j != i) continue;
        secure = lmao;
        break;
    }
    vi cool(n,0);
    for (auto it : secure) cool[it] = 1;
    int ptr = 0;
    vector<bool> msg;
    vi got(n,0);
    while (ptr < 16*pack-31) {
        for (int j = 0;j<n;j++) {
            if (!cool[j]) continue;
            if (got[j] >= f[j]) msg.push_back(R[ptr/16][j]);
            got[j]++;
            ptr++;
        }   
    }
    int bad = msg.back();
    while (msg.back() == bad) msg.pop_back();
    return msg;
}

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