Submission #728477

#	Time	Username	Problem	Language	Result	Execution time	Memory
728477		Charizard2021	Flight to the Ford (BOI22_communication)	C++17	0 / 100	797 ms	1768 KiB

communication

#include<bits/stdc++.h>
#include<communication.h>
using namespace std;
using ll = long long;
mt19937 rngQ(23478123);

ll K = rngQ();

void encode(int N, int X) {
    vector < ll > v(250, -1);
    vector < ll > b1, b2;
    mt19937 rng(K);
    for(ll i = 0; i < 250; i++){
        if(rng()%3 == 1 && (!i || v[i - 1] == -1) ){
            v[i] = rng()%2;
        }else{
            if(rng()%2) b1.push_back(i);
            else b2.push_back(i);
        }
    }
    for(auto u : b1) v[u] = (1 << 0) & X;
    for(auto u : b2) v[u] = (X >> 1) & 1;
    for(auto u : v) send(u);
    return;
}

std::pair<int, int> decode(int N) {
    vector < ll > v(250, -1);
    mt19937 rng2(K);
    vector < ll > rem, b1, b2;
    for(ll i = 0; i < 250; i++){
        if(rng2()%3 == 1 && (!i || v[i - 1] == -1) ){
            v[i] = rng2()%2;
        }else{
            if(rng2()%2) b1.push_back(i);
            else b2.push_back(i);
        }
    }
    vector < ll > g(250);
    for(ll i = 0; i < 250; i++) g[i] = receive();
    ll sure = 0, ok1 = 0, ok2 = 0, c1 = 0, c2 = 0;
    for(auto u : b1){
        if(u && v[u - 1] != -1 && v[u - 1] != g[u - 1]) sure |= g[u], ok1 = 1;
        if(u + 1 < 250 && v[u + 1] != -1 && v[u + 1] != g[u + 1]) sure |= g[u], ok1 = 1;
        c1 += (g[u] == 0 ? -1 : 1);
    }
    for(auto u : b2){
        if(u && v[u - 1] != -1 && v[u - 1] != g[u - 1]) sure |= (g[u] << 1), ok2 = 1;
        if(u + 1 < 250 && v[u + 1] != -1 && v[u + 1] != g[u + 1]) sure |= (g[u] << 1), ok2 = 1;
        c2 += (g[u] == 0 ? -1 : 1);
    }
    ll a1 = sure, a2 = sure;
    if(!ok1 && !ok2){
        if(max(c1, c2) == c1){
            if(c1 >= 0) a1 |= 1, a2 |= 1;
            if(c2 >= 0) a2 |= 2;
        }else{
            if(c2 >= 0) a1 |= 2, a2 |= 2;
            if(c1 >= 0) a1 |= 1;
        }
    }else{
        if(!ok1 && c1 >= 0) a1 |= 1;
        if(!ok2 && c2 >= 0) a1 |= 2;
    }
    a1 = min(a1, (long long)N);
    a1 = max((long long)1 , a1);
    a2 = max((long long)1 , a2);
    a2 = min(a2, (long long)N);
    assert(1 <= min(a1, a2) && max(a1, a2) <= N);
    while(a1 == a2){
        a1++;
        if(a1 == N+1) a1 = 1;
    }
    return {a1, a2};
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85