Submission #1166195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166195		kim	Message (IOI24_message)	C++20	27.43 / 100	551 ms	868 KiB

message

#include "message.h"
#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define sz(x) (int)x.size()

void send_message(std::vector<bool> M, std::vector<bool> C) {
  int S=sz(M);
  
  vector<vector<bool>> vecvec;
  for(int i=0;i!=S;){
    vector<bool> vec(31);
    for(int j=0;j<31 && i!=S;++j) if(!C[j]) vec[j]=M[i++];
    vecvec.eb(vec);
  }

  vector<bool> vecbitS(31);
  for(int i=0,j=0;(1<<i)<=S;++i,++j){
    while(C[j]) ++j;
    vecbitS[j]=((S>>i)&1);
  }

  vector<int> top5;
  vector<vector<bool>> vecCid(15,vector<bool>(31));
  for(int i=0;i<31&&sz(top5)!=5;++i) if(!C[i]) top5.eb(i);
  for(int i=0,k=0;i<31;++i) if(C[i]){
    for(int j=0;j<5;++j) vecCid[k][top5[j]]=((i>>j)&1);
    ++k;
  }


  for(int i=0;i<5;++i) send_packet(vector<bool>(31,(top5[0]>>i)&1));
  for(int i=0;i<5;++i) send_packet(vector<bool>(31,(top5[1]>>i)&1));
  {
    vector<bool> tmp,tmp2(31);
    for(int i=0;i<5;++i) tmp.eb((top5[2]>>i)&1);
    for(int i=0;i<5;++i) tmp.eb((top5[3]>>i)&1);
    for(int i=0;i<5;++i) tmp.eb((top5[4]>>i)&1);
    for(int i=0;i<=14;i+=2){
      tmp2[top5[0]]=tmp[i];
      if(i+1<15) tmp2[top5[1]]=tmp[i+1];
      send_packet(tmp2);
    }
  }
  for(auto &vec:vecCid) send_packet(vec);
  send_packet(vecbitS);
  for(auto &vec:vecvec) send_packet(vec);
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
  vector<bool> C(31);
  
  vector<int> top5;
  for(int k=0;k<2;++k){
    int id=0;
    for(int i=0;i<5;++i){
      array<int,2> cnt{0,0};
      for(int j=0;j<31;++j) ++cnt[R[5*k+i][j]];
      if(cnt[0]<cnt[1]) id|=(1<<i);
    }
    top5.eb(id);
  }
  vector<bool> tmp;
  for(int k=10;k<=17;++k){
    tmp.eb(R[k][top5[0]]);
    if(k!=17) tmp.eb(R[k][top5[1]]);
  }
  for(int i=0;i<3;++i){
    int id=0;
    for(int j=0;j<5;++j){
      id|=(tmp[5*i+j]<<j);
    }
    top5.eb(id);
  }
  for(int i=18;i<33;++i){
    int id=0;
    for(int j=0;j<5;++j) id|=(R[i][top5[j]]<<j);
    C[id]=1;
  }
  int K=33;

  int S=0;
  for(int i=0,j=0;i<31;++i) if(!C[i]) S|=(R[K][i]<<j), ++j;
  vector<bool> M(S);
  for(int i=K+1,j=0;i<sz(R) && j!=S;++i){
    for(int k=0;k<31 && j!=S;++k){
      if(!C[k]){
        M[j++]=R[i][k];
      }
    }
  }
  return M;
}
/*
2
4
0 1 1 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1

31
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
*/

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