Submission #1175803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175803		_8_8_	Message (IOI24_message)	C++20	0 / 100	75 ms	856 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(123321);
    // shuffle(p.begin(), p.end(), rng);
    vector<int> mem;
    for(int i = 0; i < B; i++) {
        if(!c[p[i]]) {
            mem.push_back(p[i]);
            s.assign(B, 0);
            send_packet(s);
            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);
                k += m;
            }
            break;
        } else {
            s.assign(B, 1);
            send_packet(s);
        }
    }
    sort(mem.begin(), mem.end());
    int sz = (int)a.size();
    for(int j = 0; j < F; j++) {
        s[mem[j]] = ((sz >> j) & 1);
    }
    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(123321);
    // 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(; (int)mem.size() < 16; it++) {
        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;
    }
    sort(mem.begin(), mem.end());
    int sz = 0;
    for(int j = 0; j < F; j++) {
        if(R[it][mem[j]]) { 
            sz += (1 << j);
        }
    }
    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: 0 / 10
• Subtask 2: 0 / 90