#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){
if(N == 3) {
vector<int> seq;
if(X == 1) seq = {0, 0, 0, 0, 0};
else if(X == 3) seq = {1, 0, 1, 1, 0};
else seq = {1, 1, 1, 1, 1};
for(int x: seq) {
send(x);
}
return;
}
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[ans]&(1<<i)) cur.pb(send(1));
else cur.pb(send(0));
}
for(int i=0;i<4;i++){
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);*/
if(N == 3) {
vector<int> g;
for(int i=0; i<5; i++) g.push_back(receive());
int cnt = 0;
for(int i=0; i<5; i++) cnt += g[i];
vector<int> h121 = {1, 0, 1, 0, 1};
vector<int> h122 = {0, 1, 0, 1, 0};
if(g == h121 || g == h122) return {1, 2};
else if(cnt < 3) return {1, 3};
else return {2, 3};
}
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){
break;
}
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);
}
}
}
}
vector<int> ans;
for(auto j:v){
for(int i=j.fi;i<=j.se;i++) ans.pb(i);
}
if(ans.size()==1) return {ans[0],ans[0]};
else return {ans[0],ans[1]};
}
/*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.");
}*/
Compilation message
communication.cpp: In function 'void encode(int, int)':
communication.cpp:92:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(int j=0;j<v.size();j++){
| ~^~~~~~~~~
communication.cpp:124:22: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
124 | if(cur[i]=1){
communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:164:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | for(int j=0;j<v.size();j++){
| ~^~~~~~~~~
communication.cpp:153:9: warning: unused variable 'a' [-Wunused-variable]
153 | int a[4]={0,6,9,15};
| ^
communication.cpp: In function 'void encode(int, int)':
communication.cpp:120:21: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
120 | if(a[ans]&(1<<i)) cur.pb(send(1));
| ~~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
2744 KB |
Output is correct |
| 2 |
Correct |
9 ms |
2756 KB |
Output is correct |
| 3 |
Correct |
14 ms |
2744 KB |
Output is correct |
| 4 |
Correct |
6 ms |
2784 KB |
Output is correct |
| 5 |
Correct |
11 ms |
2740 KB |
Output is correct |
| 6 |
Correct |
17 ms |
3080 KB |
Output is correct |
| 7 |
Correct |
34 ms |
2732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
336 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
