| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 993933 | MarwenElarbi | Flight to the Ford (BOI22_communication) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include<vector>
#include<cstdio>
#include<set>
#include<cstdlib>
#include<cstdarg>
#include<cassert>
#include"communication.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
const int nax=2e5+5;
/*void __attribute__((noreturn)) __attribute__((format(printf, 1, 2))) result(const char *msg, ...)
{
va_list args;
va_start(args, msg);
vfprintf(stdout, msg, args);
fprintf(stdout, "\n");
va_end(args);
exit(0);
}
namespace
{
enum { ENCODE, DECODE } current_phase;
int N, X;
vector<int> signals;
size_t cursor = 0;
bool flipped = false;
}
int send(int s)
{
if(current_phase == DECODE or (s != 0 and s != 1))
result("Invalid send.");
printf("send(%d) -> ", s); fflush(stdout);
int answer;
if(scanf("%d", &answer) != 1 or (answer != 0 and answer != 1))
result("Invalid reply to send.");
bool flipped_now = (s != answer);
if(flipped and flipped_now)
result("Invalid reply to send");
flipped = flipped_now;
signals.push_back(answer);
if(signals.size() > (size_t) 250)
result("Looks (and smells) fishy.");
return signals.back();
}
int receive()
{
if(current_phase == ENCODE) result("Invalid receive.");
if(cursor >= signals.size()) result("Assistant waiting for Godot.");
int r = signals[cursor++];
printf("receive() -> %d\n", r);
return r;
}*/
void encode(int N, int X){
vector<pair<int,int>> v;
v.pb({1,N});
int a[4]={0,6,9,15};
while(true){
int value=0;
for(auto j:v) value+=j.se-j.fi+1;
if(value<=2) return;
int sz[4]={value/4,value/4,value/4,value-3*(value/4)};
vector<pair<int,int>> tab[4];
for(int i=0;i<4;i++){
int sum=0;
for(int j=0;j<v.size();j++){
sum+=v[j].se-v[j].fi+1;
if(sum>=sz[i]){
int diff=sum-sz[i];
tab[i].pb({v[j].fi,v[j].se-diff});
v[j].fi=v[j].se-diff+1;
break;
}else if(v[j].fi<=v[j].se){
tab[i].pb({v[j].fi,v[j].se});
v[j].fi=0;
v[j].se=-1;
}
}
}
v.clear();
int ans;
for(int i=0;i<4;i++){
bool test=false;
for(auto j:tab[i]){
if(j.fi<=X&&X<=j.se) test=true;
}
if(test){
ans=i;
break;
}
}
vector<int> cur;
for(int i=0;i<4;i++){
if(a[i]&(1<<i)) cur+=((send(1)&1)<<i);
else cur+=((send(0)&1)<<i);
}
for(int i=0;i<4;i++){
int nab=cur^a[i];
bool bits[4];
for (int j = 0; j < 4; ++j)
{
bits[j]=( (nab&(1<<j)) ? 1 : 0 )
}
bool test=false;
for (int j = 0; j < 3; ++j)
{
test|=(bits[j]==bits[j+1]&&bits[j]==1);
}
if(test) continue;
if(cur[i]==1){
for(auto j:tab[i]){
v.pb(j);
}
}
}
}
}
std::pair<int, int> decode(int N){
/*vector<vector<string>> tab(4 , vector<string>(8));
tab[0]={"0000","0001","0010","0100","0101","1000","1001","1010"}; // 0000
tab[1]={"0000","0001","0011","1000","1001","1011","1100","1101"}; // 1001
tab[2]={"0010","0011","0100","0110","0111","1100","1110","1111"}; // 0110
tab[3]={"0101","0110","0111","1010","1011","1101","1110","1111"}; // 1111
set<string> st;
for(int i=0;i<4;i++)
for(auto u:tab[i]) st.insert(u);*/
vector<pair<int,int>> v;
v.pb({1,N});
int a[4]={0,6,9,15};
while(true){
int value=0;
for(auto j:v) value+=j.se-j.fi+1;
if(value<=2){
if(v.size()==2) return {v[0].fi,v[1].fi};
else return {v[0].fi,v[0].se};
}
int sz[4]={value/4,value/4,value/4,value-3*(value/4)};
vector<pair<int,int>> tab[4];
for(int i=0;i<4;i++){
int sum=0;
for(int j=0;j<v.size();j++){
sum+=v[j].se-v[j].fi+1;
if(sum>=sz[i]){
int diff=sum-sz[i];
tab[i].pb({v[j].fi,v[j].se-diff});
v[j].fi=v[j].se-diff+1;
break;
}else if(v[j].fi<=v[j].se){
tab[i].pb({v[j].fi,v[j].se});
v[j].fi=0;
v[j].se=-1;
}
}
}
v.clear();
vector<int> cur;
for(int i=0;i<4;i++){
cur.pb(receive());
}
for(int i=0;i<4;i++){
if(cur[i]){
for(auto j:tab[i]){
v.pb(j);
}
}
}
}
}
/*int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
if(scanf("%d %d", &N, &X) != 2 or X < 1 or X > N)
result("Invalid input.");
current_phase = ENCODE;
encode(N, X);
current_phase = DECODE;
auto r = decode(N);
if(r.first < 1 or r.first > N or r.second < 1 or r.second > N)
result("Invalid answer.");
if(r.first == X or r.second == X)
result("Correct: %d signals sent.", (int) signals.size());
else
result("Wrong answer.");
}*/