제출 #1175815

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175815		_8_8_	Message (IOI24_message)	C++20	53.89 / 100	441 ms	880 KiB

message

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

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

mt19937 rng(123321);
void send_message(vector<bool> a, vector<bool> c) {
    vector<bool> s(B, false);
    vector<int> p(B);
    iota(p.begin(), p.end(), 0);
    rng.seed(B * B * B + F);
    shuffle(p.begin(), p.end(), rng);
    vector<int> mem;
    int tot = 0;
    for(int i = 0; i < B; i++) {
        if(!c[p[i]]) {
            mem.push_back(p[i]);
            s.assign(B, 0);
            send_packet(s);
            tot++;
            for(int k = i + 1; k < B;) {
                for(int j = 0; j < (int)mem.size() && k + j < B; j++) {
                    s[mem[j]] = c[p[k + j]];
                }
                int m = (int)mem.size();
                for(int j = 0; j < m && k + j < B; j++) {
                    if(!c[p[k + j]]) {
                        mem.push_back(p[k + j]);
                    }
                }
                send_packet(s);
                tot++;
                k += m;
            }
            break;
        } else {
            s.assign(B, (c[p[i]]));
            send_packet(s);
            tot++;
        }
    }
    sort(mem.begin(), mem.end());
    int sz = (int)a.size();
    for(int j = 0; j < F; j++) {
        s[mem[j]] = ((sz >> j) & 1);
    }
    // cout << tot << "x\n";
    send_packet(s);
    for(int k = 0; k < sz; k += F) {
        for(int j = k; j < min(sz, k + F); j++) {
            s[mem[j - k]] = (a[j]);
        }
        send_packet(s);
    }
}
vector<bool> receive_message(vector<vector<bool>> R) {
    vector<bool> res;
    
    vector<int> p(B);
    iota(p.begin(), p.end(), 0);
    rng.seed(B * B * B + F);
    shuffle(p.begin(), p.end(), rng);
    int it = 0, n = (int)R.size();
    vector<int> mem;
    for(; it < n; it++) {
        int x = 0, y = 0;
        for(auto j : R[it]) {
            if(!j) x++;
            else y++;
        }
        if(x > y) {
            mem.push_back(p[it]);
            it++;
            break;
        }
    }
    int k = it;
    for(; k < B;) {
        int m = (int)mem.size();
        vector<int> nv;
        int pt = 0;
        for(int j : mem) {
            if(!R[it][j]) {
                if(k + pt < B) nv.push_back(p[k + pt]);
            }
            pt++;
        }
        for(int f : nv) {
            mem.push_back(f);
        }
        k += m;
        it++;
    }
    sort(mem.begin(), mem.end());
    int sz = 0;
    // cout << it << ' ';
    for(int j = 0; j < F; j++) {
        // cout << mem[j] << ' ';
        if(R[it][mem[j]]) { 
            sz += (1 << j);
        }
    }
    // cout << sz << '\n';
    it++;
    res.resize(sz);
    for(int k = 0; k < sz; k += F) {
        for(int j = k; j < min(sz, k + F); j++) {
            res[j] = R[it][mem[j - k]];
        }
        it++;
    }
    return res;    
}

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