Submission #1242107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242107		mychecksedad	Message (IOI24_message)	C++20	87.16 / 100	389 ms	872 KiB

message

#include "message.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define ll long long int
const int N = 1e5+100;


void send_message(std::vector<bool> e, std::vector<bool> C) {
  vi P, d(16);

  for(int i = 0; i < 31; ++i) if(C[i] == 0) P.pb(i);
  for(int i = 0; i < 16; ++i) d[i] = (i == 15 ? P[0] + 31 - P[i]: P[i + 1] - P[i]) - 1;
  // for(int x: d) cerr << x << ' ';
  for(int i = 0; i < 4; ++i){
    vector<bool> m(31);
    for(int j = 0; j < 16; ++j){
      if((1<<i)&d[j]){
        m[P[j]] = 1;
      }else{
        m[P[j]] = 0;
      }
    }
    send_packet(m);
  }
  int sz = (int) e.size();

  vector<bool> mm(31);
  for(int i = 0; i <= 10; ++i){
    if((1<<i)&sz){
      mm[P[i]] = 1;
    }
  }
  send_packet(mm);

  for(int i = 0; i < e.size(); ){
    vector<bool> m(31);
    for(int j = 0; j < 16; ++i, ++j){
      m[P[j]] = e[i];
    }
    send_packet(m);
  }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
  vi go(31);
  for(int i = 0; i < 4; ++i){
    for(int j = 0; j < 31; ++j){
      go[j] += (1<<i)*R[i][j];
    }
  }
  for(int j = 0; j < 31; ++j) go[j] = (j + go[j] + 1) % 31;

  vi T;
  vector<bool> nice(31);
  for(int i = 0; i < 31; ++i){
    int v = i;
    int cnt = 0;
    vector<bool> vis(31);
    T.clear();
    while(!vis[v]){
      T.pb(v);
      vis[v] = 1;
      v = go[v];
      cnt++;
    }
    if(cnt == 16){
      for(int x: T) nice[x] = 1;
      break;
    }
  }

  int sz = 0;
  for(int j = 0; j <= 10; ++j){
    sz += (1<<j)*(R[4][T[j]]);
  }

  vector<bool> res;
  for(int i = 5; i < (int) R.size(); ++i){
    for(int j = 0; j < 31; ++j){
      if(nice[j]) res.pb(R[i][j]);
    }
  }
  while((int)res.size() > sz) res.pop_back();

  return res;
}

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