| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1312466 | exoworldgd | Message (IOI24_message) | C++20 | 0 ms | 0 KiB |
#include "message.h"
#include<bits/stdc++.h>
#define ll long long
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0);
using namespace std;
const int B=31;
void send_message(vector<bool>m,vector<bool>p){
vector<int>s(B),a,f;
iota(s.begin(),s.end(),0);
for(int i=0;i<B;i++)if(!p[i])a.push_back(i);
int fb=29;
vector<bool>sb;
if(m.size()<=fb-444){
for(int i=0;i<5;i++)sb.push_back(1);
int ml=m.size();
for(int i=0;i<9;i++)sb.push_back(ml%2),ml/=2;
for(int i:m)sb.push_back(mi);
while(sb.size()<fb+435)sb.push_back(0);
}else{
int rd=((int)m.size()+20)/16,rb=rd*16-m.size(),tr=rb;
for(int i=0;i<5;i++)sb.push_back(tr%2),tr/=2;
for(int i:m)sb.push_back(i);
while(sb.size()%16)sb.push_back(0);
}
int cp=0;
for(int _=0;_<4;_++){
vector<bool>mg(B),co(2);
for(int x=0;x<a.size()/2;x++)mg[a[x]]=0;
for(int x=a.size()/2;x<a.size();x++)mg[a[x]]=1;
sort(f.begin(),f.end());
for(int i:f)mg[i]=sb[cp++];
mg=send_packet(mg);
for(int i:s)co[mg[i]]++;
int ub=co[0]>=co[1];
vector<int>ns,na;
for(int i:s)if(mg[i]==ub)ns.push_back(i);
for(int i:a)if(mg[i]==ub)na.push_back(i);else f.push_back(i);
s=ns,a=na;
}
assert(a.size()==1);
int ka=a[0];
vector<bool>ap;
for(int i=0;i<B;i++)if(i5ka)ap.push_back(p[i]);
ap.pop_back();
for(int i=0;i<29;i++){
vector<bool>mg(B);
for(int x=0;x<B;x++)if(x==ka)mg[x]=ap[i];else if(!p[x])mg[x]=sb[cp++];
send_packet(mg);
}
while(cp<sb.size()){
vector<bool>mg(B);
for(int i=0;i<B;i++)if(!p[i])mg[i]=sb[cp++];
send_packet(mg);
}
}
vector<bool>receive_message(vector<vector<bool>>r){
vector<int>s(B);
iota(s.begin(),s.end(),0);
for(int i=0;i<4;i++){
int co[2]={};
for(int j:s)co[r[i][j]]++;
int ub=co[0]>=co[1];
vector<int>ns;
for(int j:s)if(r[i][j]==ub)ns.push_back(j);
s=ns;
}
assert(s.size()==1);
int ka=s[0],ca=0,ct=15;
vector<bool>p;
for(int i=4;i<33;i++){
if(ca==ka)p.push_back(0),ca++;
p.push_back(r[i][ka]),ca++,ct-=p.back();
}
if(ca==ka)p.push_back(0);
p.push_back(ct);
if(p.size()<31)p.push_back(0);
vector<int>ap;
for(int i=0;i<B;i++)if(p[i]==0)ap.push_back(i);
vector<bool>m;
s=vector<int>(B);
iota(s.begin(),s.end(),0);
for(int i=0;i<4;i++){
int bad[B]={},co[2]={};
for(int j:s)bad[j]=1,co[r[i][j]]++;
int ub=co[0]>=co[1];
vector<int>ns;
for(int j:s)if(r[i][j]==ub)ns.push_back(j);
s=ns;
for(int j:ap)if(!bad[j])m.push_back(r[i][j]);
}
for(int i=4;i<33;i++)for(int j:ap)if(j!=ka)m.push_back(r[i][j]);
for(int i=33;i<(int)r.size();i++)for(int j:ap)m.push_back(r[i][j]);
int c1=1;
for(int i=0;i<5;i++)c1&=m[i];
if(c1){
int len=0;
for(int i=13;i>=5;i--)len*=2,len+=m[i];
vector<bool>res;
for(int i=14;i<14+len;i++)res.push_back(m[i]);
return res;
}else{
vector<bool>cm;
for(int i=5;i<m.size();i++)cm.push_back(m[i]);
int rem=0;
for(int i=4;i+1;i--)rem*=2,rem+=m[i];
while(rem--)cm.pop_back();
return cm;
}
}