Submission #1200813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200813		Pacybwoah	Message (IOI24_message)	C++20	100 / 100	393 ms	856 KiB

message

#include "message.h"
#include<iostream>
#include<algorithm>
#include<utility>
#include<map>
#include<vector>
using namespace std;
typedef long long ll;
namespace{
    const int q = 66, n = 31;
}

void send_message(std::vector<bool> M, std::vector<bool> C){
    vector<vector<bool>> send(q, vector<bool>(n));
    vector<int> imp;
    for(int i = 0; i < n; i++) if(!C[i]) imp.push_back(i);
    int cur = 0;
    int s = (int)M.size();
    M.push_back(0);
    for(int i = 0; i < 1024 - s; i++) M.push_back(1);
    int cnt = 0;
    for(int i = 0; i < n; i++){
        if(C[i]) continue;
        int diff = (-i + n + imp[(cnt + 1) % 16]) % n;
        cnt++;
        for(int j = 0; j < diff - 1; j++) send[j][i] = 0;
        send[diff - 1][i] = 1;
        for(int j = diff; j < q; j++){
            send[j][i] = M[cur];
            cur++;
        }
    }
    for(int i = 0; i < q; i++) send_packet(send[i]);
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R){
    vector<int> nxt(n);
    for(int i = 0; i < n; i++){
        int fst = 0;
        for(int j = 0; j < q; j++){
            if(R[j][i] == 1){
                fst = j + 1;
                break;
            }
        }
        nxt[i] = (i + fst) % n;
        //cout << i << " " << nxt[i] << endl;
    }
    vector<int> imp;
    for(int i = 0; i < n; i++){
        vector<int> vis(n);
        int cnt = 0, now = i;
        for(int j = 0; j < 16; j++){
            if(vis[now] == 0) cnt++;
            vis[now] = 1;
            now = nxt[now];
        }
        if(cnt == 16 && now == i){
            for(int j = 0; j < n; j++){
                if(vis[j]) imp.push_back(j);
            }
            break;
        }
    }
    sort(imp.begin(), imp.end());
    vector<bool> ans;
    for(auto &x: imp){
        bool flag = 0;
        for(int i = 0; i < q; i++){
            if(flag){
                ans.push_back(R[i][x]);
            }
            else if(R[i][x]) flag = 1;
        }
    }
    while(ans.back() != 0) ans.pop_back();
    ans.pop_back();
    return ans;
}

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