Submission #1199108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199108		sqrtxsunlight	Message (IOI24_message)	C++20	79.64 / 100	424 ms	852 KiB

message

#include "message.h"
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;


vector<bool> send_packet2(vector<bool> A){
  // for(int i=0;i<A.size();i++)cerr << A[i] << " ";
  // cerr << endl;
  return send_packet(A);
}


void send_message(vector<bool> M, vector<bool> C) {

  // for(int i = 0;i<M.size();i++){
  //   vector<bool> A(31, M[i]);
  //   send_packet2(A);
  // }
  // return;
    
  int first = 0,first2;
  for(int i=0;i<31;i++){if(C[i] == 0){first = i;break;}}
  first2 = first;
  
  for(int i=0;i<4;i++){
    vector<bool> A(31, first%2);
    send_packet2(A);
    first/=2;
  }
  first = first2;
  
  int n = M.size();
  vector<bool> order (11,0);
  for(int i=0;i<11;i++){
    order[i] = n%2;
    n/=2;
  }
  reverse(order.begin(),order.end());
  vector<bool> A (31, 0);
  int j = 0;
  int cnt = first+1;
  n = M.size();
  for(int i=0;i<31;i++){
    if(C[i])continue;
    if(i == first){
      A[i] = C[cnt];
      cnt ++;
      j--;
    }
    else if(j < 11)
      A[i] = order[j];
    else{
      int k = j-11;
      if(k < n){
        A[i] = M[k];
      }
    }
    j++;
  }
  send_packet2(A);
  
  j -= 11;
  
  while(cnt < 31){
    A = vector<bool> (31, 0);
    for(int i=0;i<31;i++){
      if(C[i])continue;
      if(i == first){
        A[i] = C[cnt];
        cnt ++;
      }else{
        if(j < n){
          A[i] = M[j];
          j++;
        }
      }
    }
    send_packet2(A);
  }
  
  if(j>=n)return;
  
  while(j<n){
    A = vector<bool> (31, 0);
    for(int i=0;i<31;i++){
      if(C[i])continue;
      if(j < n){
        A[i] = M[j];
        j++;
      }
    }
    send_packet2(A);
  }
}

vector<bool> receive_message(vector<vector<bool> > R) {
  // vector<bool> M(R.size(),0);
  // for(int i = 0;i<R.size();i++){
  //   int val = 0;
  //   for(int j=0;j<31;j++)if(R[i][j] == 1)val+=1;
  //   if(val > 15)M[i] = 1;
  // }

  // return M;

  // cerr << "GOT" << endl;
  
  vector<bool> M;
  vector<bool> C(31,1);
  int first = 0;
  for(int i=3;i>=0;i--){
    int val = 0;
    for(int j=0;j<31;j++)if(R[i][j] == 1)val+=1;
    first *= 2;
    if(val > 15){
        first += 1;
    }
  }

  // cerr << first << endl;
  
  C[first] = 0;
  
  int cnt = 4;
  for(int i = first+1;i<31;i++){
      C[i] = R[cnt][first];
      cnt ++;
  }

  // for(int i =0;i<31;i++)cerr << C[i] << " ";
  // cerr << endl;
  
  int n = 0;
  int cnt2 = 0;
  for(int i=0;i<31;i++){
      if(C[i])continue;
      if(i==first)continue;
      if(cnt2 > 10){
          M.push_back(R[4][i]);
          continue;
      }
      n *= 2;
      n += R[4][i];
      cnt2 ++;
  }

  // cerr << n << endl;
  
  for(int i=5;i<R.size();i++){
      for(int j=0;j<31;j++){
          if(C[j]) continue;
          if(cnt > i && j == first)continue;
          M.push_back(R[i][j]);
      }
  }
  
  vector<bool> ans;
  for(int i=0;i<n;i++)ans.push_back(M[i]);
  
  
  return ans;
}

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