Submission #1243961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243961		AlperenT_	Message (IOI24_message)	C++20	58.63 / 100	463 ms	880 KiB

message

#include "message.h"
#include <bits/stdc++.h> 
#pragma GCC optimize("O3,unroll-loops") 
#pragma GCC target("avx2") 
#define pb push_back
#define F first
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long 
using namespace std ;
const int maxn = 500 + 100 , inf = 1e9 , mod = 998244353;
int mark[maxn] , c[maxn ]; 
int p[] = {24,18,28,13,5,26,2,7,27,4,21,0,11,22,14,8,17,29,25,9,3,19,6,15,1,23,16,20,30,12,10} ; 
int ch(){
  int t0 = 16 , t1 = 15 ;
  rep(i , 0 ,30){
    if(mark[i] == 1){
      if(c[i] == 0)t0-- ;
      if(c[i] == 1)t1--;
    }
  }
  if(t0 > t1)return 1 ;
  return 0 ;
}
int cp[maxn] ;
void send_message(std::vector<bool> M, std::vector<bool> C) {
  rep(i , 0 ,30)cp[i]=C[i]; 
  rep(i , 0 ,30)c[i] =C[i] ;
  rep(i , 0 ,30)mark[i] = 0;  
  int ted= 0 , f =0 ;
  vector <int> az ;
  while(ted != 31){
    vector <bool> a ;vector <int> az2 , az3;
    rep(i , 0 ,30)a.pb(0) ;
    int s = sz(az) , id =0  ;
    while(ted!=31 && id!=s){
      a[az[id]] = C[p[ted]] ;
      if(C[p[ted]]==0)az2.pb(p[ted]) ;
      else az3.pb(p[ted]);
      id++;
      ted++ ;
    }
    if(ch() && ted != 31){
      rep(i , 0 ,30){
        if(mark[i] == 0){
          a[i] = C[p[ted]];
        }
      }
      if(C[p[ted]] == 0)az2.pb(p[ted]) ;
      else az3.pb(p[ted]) ;
      ted++ ;
    }
    send_packet(a) ;
    f++ ;
    for(int x : az2){az.pb(x) ;mark[x] = 1;}
    for(int x : az3){mark[x] =1 ;}
  }
  vector <bool> sz ;
  int bit =0 ;
  rep(i , 0 ,30){
    if(C[i]==1){
      sz.pb(0);
      continue;
    }
    sz.pb(sz(M)>>bit&1);
    bit++ ;
  }
  send_packet(sz); 
  vector <bool> o ;
  rep(i , 0 ,sz(M)-1){
    o.pb(M[i]) ;
    if(i==sz(M)-1 || sz(o) ==16){
      vector <bool> vec ;
      int id = 0 ;
      rep(i , 0 ,30){
        if(C[i] == 1){
          vec.pb(0) ;
        }else{
          if(id == sz(o)){
            vec.pb(0);
          }else{
            vec.pb(o[id]) ;
            id++;
          }
        }
      }
      o.clear() ;
      send_packet(vec) ;
    }
  }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
  rep(i , 0 ,30)c[i] = 1; 
  rep(i , 0 ,31)mark[i] =0 ;
  int ted= 0 , f =0 ;
  vector <int> az ;int cnt =0 ; 
  while(ted != 31){
  //  cout << "st---\n" ;
    vector <bool> a = R[cnt] ;vector <int> az2 , az3  ;cnt++ ;
    int s = sz(az) , id =0  ;
    while(ted!=31 && id!=s){
      c[p[ted]] = a[az[id]] ;
      if(c[p[ted]]==0)az2.pb(p[ted]) ;
      else az3.pb(p[ted]) ;
  //    cout << p[ted] << " : " << cp[p[ted]] << " " << c[p[ted]] << "<--\n" ;
      id++;
      ted++ ;
    }
    if(ch() && ted != 31){
      int sm =0 ;
      rep(i , 0 ,30){
        if(mark[i] == 1)continue ;
        if(a[i] == 1)sm++;
        else sm-- ;
      }
      if(sm > 0){
        c[p[ted]] = 1; 
      }else{
        c[p[ted]] = 0 ;
      }
  ///    cout << p[ted] << " : " << cp[p[ted]] << " " << c[p[ted]] << "<--\n" ;
      if(c[p[ted]] == 0)az2.pb(p[ted]) ;
      else az3.pb(p[ted]);
      ted++ ;
    }
    f++ ;
    for(int x : az2){mark[x] = 1; az.pb(x) ;}
    for(int x : az3)mark[x] = 1; 
  //  cout <<sz(az) << "<-----------------------\n"; 
  //  cout << "en" ;
  }
 // cout << "\n" ;
 // rep(i , 0 ,30)cout << c[i] ;
//cout << '\n' ;
  vector <bool> sz = R[cnt];cnt++;
  int rs =0  ,bit= 0;
  rep(i , 0, 30){
    if(c[i] == 1)continue ;
    rs += (1<<bit) * sz[i] ;
    bit++ ;
  }
  int u = 0; 
  vector <bool> m ;
  while(sz(m) != rs){
    vector <bool> a = R[cnt] ;cnt++ ;
    rep(i , 0 ,30){
      if(sz(m)==rs)continue ;
      if(c[i] == 1)continue ;
      m.pb(a[i]) ;
    }
  }
  return m ; 
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 48.6324 / 90