Submission #829503

#TimeUsernameProblemLanguageResultExecution timeMemory
829503QwertyPiFlight to the Ford (BOI22_communication)C++17
0 / 100
299 ms200 KiB
#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); } bits.push_back(b1); continue; } }else{ int s4 = receive(); if(s2 == s4){ link(b2, B, s4); }else{ link(b1, b2, s1 ^ s2); } 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]);
      |             ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...