Submission #1217523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217523		dosts	Message (IOI24_message)	C++20	42.26 / 100	485 ms	880 KiB

message

#include "message.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
vi v;
void rando() {
  if (!v.empty()) return;
  for (int i = 0;i<31;i++) v.push_back(i);
  shuffle(all(v),mt19937(23));
}
void send_message(std::vector<bool> M, std::vector<bool> C) {
  rando();
  std::vector<bool> A(31, 0);
  vi clean;
  int cleany = 0;
  for (int i = 0;i<31;i++) {
    for (int j = 0;j<31;j++) A[j] = C[v[i]];
    if (!C[v[i]]) clean.push_back(v[i]),cleany+=(i<18);
    if (i < 18) send_packet(A);
  }
  if (cleany > 3) {
    int nxt = 18;
    //tüm shitler bulunmadıysa
    for (int j = 0;nxt<31;j++) {
      A.assign(31,0);
      int ctr = 0;
      for (int i = 0;i<cleany && nxt < 31;i++) {
        if (C[v[nxt]] == 0) ctr++;
        A[clean[i]] = C[v[nxt++]];
      }
      cleany+=ctr;
      send_packet(A);
    }
  }
  int  S = big(M);
  vector<bool> szpack(31,0);
  for (int i = 0;i<11;i++) {
    szpack[clean[i]] = !!(S&(1<<i));
  }
  send_packet(szpack);
  int j = 0;
  for (int i = 0;i<(S+15)/16;i++) {
    int ptr = 0;
    for(int t = 0;t<16;t++) {
      A[clean[ptr++]] = M[j++];
    }
    send_packet(A);
  }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
  rando();
  int rsz = R.size();
/*   for (int i = 0;i<rsz;i++) {
    for (int j = 0;j<31;j++) cerr << R[i][j];
    cerr << '\n';
  } */
  vi clean;
  for (int i = 0;i<18;i++) {
    int z = 0,o = 0;
    for (auto it : R[i]) {
      if (it) o++;
      else z++;
    }
    if (z > o) clean.push_back(v[i]);
  }
  int curr = 18;
  int cleany = big(clean);
  if (big(clean) > 3) {
    int nxt = 18;
    for (int j = 0;nxt<31;j++) {
      cleany = big(clean);
      for (int k = 0;k<cleany && nxt < 31;k++) {
        if (!R[curr][clean[k]]) clean.push_back(v[nxt]);
        nxt++;
      }
      curr++;
    }
  }
  else for (int j = 18;j<31;j++) clean.push_back(v[j]);
  int s = 0;
  for (int i = 0;i<11;i++) {
    if (R[curr][clean[i]]) s+=(1<<i);
  }
  curr++;
  //cerr << s sp curr << endl;
  vector<bool> M(s);
  int j = 0;
  for (int i = 0;i<(s+15)/16;i++) {
    int ptr = 0;
    for (int t = 0;t<16;t++) {
      M[j++] = R[curr][clean[ptr++]];
    }
    curr++;
  }
  return M;
}

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