Submission #1242791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242791		noyancanturk	Message (IOI24_message)	C++20	95 / 100	441 ms	868 KiB

message

#include "message.h"

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define has(x,i) (((x)>>(i))&1)
#define maxquer 67

vector<bool>debug;

void send_message(vector<bool>m,vector<bool>c){
  int top=!m.back();
  while(m.size()<5000){
    m.pb(top);
  }
  vector<vector<int>>lf,rg;
  vector<int>st1,st2;
  int ind=0;
  int asked=0;
  auto ask=[&](int toaskfrom,int guy) -> bool {
    asked++;
    vector<bool>toask(31);
    for(int i=0;i<31;i++){
      if(!c[i]&&i!=toaskfrom){
        toask[i]=m[ind++];
      }
    }
    if(toaskfrom!=-1)toask[toaskfrom]=c[guy];
    auto sent=send_packet(toask);
    return sent[toaskfrom];
  };
  int accuse[31]{};
  for(int i=0;i<31;i++){
    if(!st1.size()){
      st1.pb(i);
      continue;
    }
    int query=ask(st1.back(),i);
    if(query){
      accuse[st1.back()]|=1<<i;
      st2.pb(i);
      if(st1.size()==st2.size()){
        lf.pb(st1);
        rg.pb(st2);
        st1.clear();
        st2.clear();
      }
    }else{
      st1.pb(i);
    }
  }
  lf.pb(st1);
  rg.pb(st2);
  vector<int>good;
  int real=st1.back();
  good.pb(real);
  for(int i=0;i<lf.size();i++){
    auto l=lf[i];
    auto r=rg[i];
    reverse(l.begin(),l.end());
    for(int j:l){
      if(j==real)continue;
      int res=ask(real,j);
      if(!res){
        accuse[real]|=accuse[j];
        good.pb(j);
        if(good.size()==16)break;
      }else{
        break;
      }
    }
    if(good.size()==16)break;
    for(int j:r){
      if(has(accuse[real],j))continue;
      int res=ask(real,j);
      if(!res){
        good.pb(j);
        if(good.size()==16)break;
      }
    }
    if(good.size()==16)break;
  }
  while(asked<maxquer){
    ask(-1,0);
  }
}

vector<bool>receive_message(vector<vector<bool>>ms){
  int asked[maxquer]{};
  for(int i=0;i<maxquer;i++)asked[i]=-1;
  vector<vector<int>>lf,rg;
  vector<int>st1,st2;
  int ind=0;
  auto ask=[&](int toaskfrom) -> bool {
    asked[ind]=toaskfrom;
    vector<bool>sent=ms[ind++];
    return sent[toaskfrom];
  };
  int accuse[31]{};
  for(int i=0;i<31;i++){
    if(!st1.size()){
      st1.pb(i);
      continue;
    }
    int query=ask(st1.back());
    if(query){
      accuse[st1.back()]|=1<<i;
      st2.pb(i);
      if(st1.size()==st2.size()){
        lf.pb(st1);
        rg.pb(st2);
        st1.clear();
        st2.clear();
      }
    }else{
      st1.pb(i);
    }
  }
  lf.pb(st1);
  rg.pb(st2);
  vector<int>good;
  int real=st1.back();
  good.pb(real);
  for(int i=0;i<lf.size();i++){
    auto l=lf[i];
    auto r=rg[i];
    reverse(l.begin(),l.end());
    for(int j:l){
      if(j==real)continue;
      int res=ask(real);
      if(!res){
        accuse[real]|=accuse[j];
        good.pb(j);
        if(good.size()==16)break;
      }else{
        break;
      }
    }
    if(good.size()==16)break;
    for(int j:r){
      if(has(accuse[real],j))continue;
      int res=ask(real);
      if(!res){
        good.pb(j);
        if(good.size()==16)break;
      }
    }
    if(good.size()==16)break;
  }
  sort(good.begin(),good.end());
  vector<bool>m;
  for(int i=0;i<maxquer;i++){
    for(int j:good){
      if(j!=asked[i]){
        m.pb(ms[i][j]);
      }
    }
  }
  int top=m.back();
  while(m.back()==top){
    m.pop_back();
  }
  return m;
}

// void send_message(std::vector<bool> M, std::vector<bool> C) {
//   std::vector<bool> A(31, 0);
//   send_packet(A);
// }

// std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
//   return std::vector<bool>({0, 1, 1, 0});
// }

• Subtask 0: 0 / 0
• Subtask 1: 9.5 / 10
• Subtask 2: 85.5 / 90