Submission #829507

#	Time	Username	Problem	Language	Result	Execution time	Memory
829507		QwertyPi	Flight to the Ford (BOI22_communication)	C++17	15 / 100	664 ms	1844 KiB

communication

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

using namespace std;

//
// --- Sample implementation for the task communication ---
//
// To compile this program with the sample grader, place:
//     communication.h communication_sample.cpp sample_grader.cpp
// in a single folder, then open the terminal in this directory (right-click onto an empty spot in the directory,
// left click on "Open in terminal") and enter e.g.:
//     g++ -std=c++17 communication_sample.cpp sample_grader.cpp
// in this folder. This will create a file a.out in the current directory which you can execute from the terminal
// as ./a.out
// See task statement or sample_grader.cpp for the input specification
//
void encode(int N, int X) {
    int B = __lg(N) + 1;
    vector<int> bits; for(int j = 0; j < B; j++) bits.push_back(j);
    vector<int> a; for(int j = 0; j < B; j++) a.push_back((X & (1 << j)) > 0);
    while(bits.size() >= 2){
        int b1 = bits.back(); bits.pop_back();
        int b2 = bits.back(); bits.pop_back();

        int s1 = send(a[b1]);
        int s2 = send(a[b2]);
        int s3 = send(a[b1]);
        if(s1 == s3){
            int s4 = send(a[b1]);
            if(s3 == s4){
                bits.push_back(b2);
                continue;
            }else{
                int s5 = send(a[b2]);
                bits.push_back(b1);
                continue;
            }
        }else{
            int s4 = send(a[b2]);
            bits.push_back(b1);
        }
    }
}

struct DSU{
    int dsu[71];
    void init(){
        for(int i = 0; i < 71; i++) dsu[i] = i;
    }
    int f(int x){ return x == dsu[x] ? x : dsu[x] = f(dsu[x]); }
    void g(int x, int y){ x = f(x), y = f(y); dsu[x] = y; }
} dsu;

void link(int u, int v, bool b){
    dsu.g(u * 2, v * 2 + b);
    dsu.g(u * 2 + 1, v * 2 + !b);
}

std::pair<int, int> decode(int N) {
    int B = __lg(N) + 1;
    vector<int> bits; for(int j = 0; j < B; j++) bits.push_back(j);
    vector<int> a;
    dsu.init();
    while(bits.size() >= 2){
        int b1 = bits.back(); bits.pop_back();
        int b2 = bits.back(); bits.pop_back();

        int s1 = receive();
        int s2 = receive();
        int s3 = receive();
        if(s1 == s3){
            int s4 = receive();
            if(s3 == s4){
                link(b1, B, s4);
                bits.push_back(b2);
                continue;
            }else{
                int s5 = receive();
                if(s2 == s5){
                    link(b2, B, s5);
                }else{
                    link(b1, b2, s1 ^ s2 ^ 1);
                }
                bits.push_back(b1);
                continue;
            }
        }else{
            int s4 = receive();
            if(s2 == s4){
                link(b2, B, s4);
            }else{
                link(b1, b2, s1 ^ s2 ^ 1);
            }
            bits.push_back(b1);
        }
    }

    int sp = bits[0];
    vector<int> ans;
    for(int i = 0; i < 2; i++){
        int r = 0;
        for(int j = 0; j < B; j++){
            bool y = dsu.f(j * 2) == dsu.f(B * 2 + 1) || dsu.f(j * 2) == dsu.f(sp * 2 + (1 - i));
            r += (1 << j) * y;
        }
        ans.push_back(r);
    }
    if(ans[0] == 0) ans[0] = 1;
    if(ans[1] == 0) ans[1] = 1;
    return {ans[0], ans[1]};
}

Compilation message (stderr)

communication.cpp: In function 'void encode(int, int)':
communication.cpp:35:21: warning: unused variable 's5' [-Wunused-variable]
   35 |                 int s5 = send(a[b2]);
      |                     ^~
communication.cpp:40:17: warning: unused variable 's4' [-Wunused-variable]
   40 |             int s4 = send(a[b2]);
      |                 ^~
communication.cpp:27:13: warning: unused variable 's2' [-Wunused-variable]
   27 |         int s2 = send(a[b2]);
      |             ^~

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