Submission #1242172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242172		mychecksedad	Message (IOI24_message)	C++20	100 / 100	656 ms	920 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);

  reverse(all(e));
  int nw = 1025 - (int) e.size();
  for(int j = 0; j < nw; ++j) e.pb(1);
  reverse(all(e));
  e[nw - 1] = 0;

  // for(int x: e) cerr << x << ' ';
  // exit(0);

  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;


  int num = (31 + e.size()) / 16;
  vector<vector<bool>> m(num, vector<bool>(31));
  vector<pii> av;
  for(int j = 0; j < 16; ++j){
    for(int i = 0; i < d[j]; ++i){
      m[i][P[j]] = 1;
    }
    m[d[j]][P[j]] = 0;
    for(int i = d[j] + 1; i < num ;++i) av.pb({i, P[j]});
  }
  sort(all(av));
  // for(int x: e) cerr << x << ' ';
  // cerr << '\n';
  assert(av.size() == e.size());
  for(int i = 0; i < av.size(); ++i){
    int x = av[i].ff;
    int y = av[i].ss;
    m[x][y] = e[i];
  }
  for(auto v: m) send_packet(v);
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
  vi go(31), d(31);
  for(int j = 0; j < 31; ++j){
    go[j] = j + 1;
    for(int i = 0; i < R.size(); ++i){
      if(R[i][j] == 0) break;
      ++go[j];
    }
    d[j] = go[j] - j;
    go[j] %= 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;
    }
  }

  vector<pii> av;
  for(int j = 0; j < 31; ++j){
    if(nice[j] == 0) continue;
    for(int i = d[j]; i < R.size(); ++i) av.pb({i, j});
  }
  sort(all(av));
  vector<bool> res;
  for(int i = 0; i < av.size(); ++i) res.pb(R[av[i].ff][av[i].ss]);


  reverse(all(res));
  while(res.back() == 1) res.pop_back();
  res.pop_back();
  reverse(all(res));
  return res;
}

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