Submission #1201852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201852		Bzslayed	Message (IOI24_message)	C++20	100 / 100	440 ms	868 KiB

message

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

int nxt[31];
bool vis[31];
int cycle = 1, endp = -1;
void cycle_dfs(int x){
    vis[x] = true;
    if (!vis[nxt[x]]){
        cycle++;
        cycle_dfs(nxt[x]);
    }
    else{
        endp = nxt[x];
        return;
    }
}

void send_message(vector<bool> M, vector<bool> C){
    vector<bool> tempC;
    for (auto it : C) tempC.push_back(it);
    for (auto it : C){
        tempC.push_back(it);
        if (it == 0) break;
    }

    int dist[31];
    int prev = -1;
    for (int i=0; i<(int)tempC.size(); i++){
        if (tempC[i] == 0){
            if (prev != -1) dist[prev] = i-prev;
            prev = i;
        }
    }
    for (int i=0; i<31; i++){
      if (C[i] == 1) dist[i] = 0;
    }
    // for (int i=0; i<31; i++) cout << dist[i] << " ";
    // cout << "\n";

    int msg_len = M.size();
    vector<bool> pad_message;
    while (pad_message.size()+1+msg_len < 1025) pad_message.push_back(0);
    pad_message.push_back(1);
    for (auto it : M) pad_message.push_back(it);
    // for (auto it : pad_message) cout << it;
    // cout << "\n";

    vector<vector<bool>> packets(66, vector<bool>(31));
    vector<vector<bool>> occupied(66, vector<bool>(31));
    for (int i=0; i<31; i++){
        if (dist[i] == 0) continue;
        for (int j=0; j<dist[i]-1; j++){
          packets[j][i] = 0;
          occupied[j][i] = 1;
        }
        packets[dist[i]-1][i] = 1;
        occupied[dist[i]-1][i] = 1;
    }

    int ptr = 0;
    for (int i=0; i<66; i++){
        for (int j=0; j<31; j++){
            if (!occupied[i][j] && C[j] == 0){
                if (ptr > 1024) break;
                packets[i][j] = pad_message[ptr];
                ptr++;
            }
        }
        
        send_packet(packets[i]);
    }
    
    // cout << "testing" << "\n";
    // for (int i=0; i<66; i++){
    //   for (int j=0; j<31; j++){
    //     cout << packets[i][j] << " ";
    //   }
    //   cout << "\n";
    // }
}

vector<bool> receive_message(vector<vector<bool>> R){
    int dist_bits[31];
    for (int i=0; i<31; i++){
        for (int j=0; j<16; j++){
            if (R[j][i] == 1){
                nxt[i] = (i+j+1)%31;
                dist_bits[i] = j+1;
                break;
            }
        }
    }

    unordered_map<int, bool> not_cont;
    for (int i=0; i<31; i++){
        cycle = 1, endp = -1;
        memset(vis, false, sizeof(vis));

        cycle_dfs(i);
        if (endp != i) continue;

        if (cycle == 16){
            memset(vis, false, sizeof(vis));
            int cur = i;
            not_cont[cur] = true;
            for (int j=0; j<15; j++){
                cur = nxt[cur];
                not_cont[cur] = true;
            }

            break;
        }
    }

    for (int i=0; i<31; i++){
        if (!not_cont[i]) dist_bits[i] = 0;
    }

    vector<bool> ans;
    for (int i=0; i<66; i++){
        for (int j=0; j<31; j++){
            if (!not_cont[j]) continue;
            if (dist_bits[j] == 0) ans.push_back(R[i][j]);
            else dist_bits[j]--;
        }
    }
    
    // cout << ans.size() << "\n";
    // for (auto it : ans) cout << it;
    assert(ans.size() == 1025);
    reverse(ans.begin(), ans.end());
    bool seen = false;
    while (!seen){
        bool lst = ans.back();
        ans.pop_back();
        if (lst == 1) seen = true;
    }
    reverse(ans.begin(), ans.end());

    return ans;
}

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