Submission #1254073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254073		erdemkiraz	Message (IOI24_message)	C++20	100 / 100	381 ms	848 KiB

message

#include "message.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

void send_message(vector<bool> M, vector<bool> C) {
  M.push_back(1);
  while((int) M.size() < 1025) {
    M.push_back(0);
  }

  assert((int) M.size() == 1025);

  vector<int> v;
  vector<int> w(31, -1);
  for(int i = 0; i < 31; i++) {
    if(!C[i]) {
      w[i] = (int) v.size();
      v.push_back(i);
    }
  }
  vector<int> d;
  for(int i = 0; i < 15; i++) {
    d.push_back(v[i + 1] - v[i]);
  }
  d.push_back(31 + v[0] - v[15]);

  int it = 0;
  for(int i = 0; i < 66; i++) {
    vector<bool> A(31, 0);
    for(int j = 0; j < 31; j++) {
      if(C[j] == 0) {
        if(d[w[j]] > 0) {
          // printf("i = %d j = %d\n", i, j);
          A[j] = !--d[w[j]];
        }
        else {
          A[j] = M[it++];
        }
      }
    }
    send_packet(A);
  }
  assert(it == (int) M.size());
}

vector<bool> receive_message(vector<vector<bool>> R) {

  vector<int> go(31, -1);

  for(int i = 0; i < 31; i++) {
    int st = -1;
    for(int j = 0; j < 16; j++) {
      if(R[j][i]) {
        st = j;
        break;
      }
    }
    // printf("i = %d st = %d\n", i, st);
    if(st != -1) {
      go[i] = (i + st + 1) % 31;
    }
  }

  vector<int> goods;

  for(int i = 0; i < 31; i++) {
    int x = i;
    for(int it = 0; it < 31 and x != -1; it++) {
      x = go[x];
    }
    if(x == -1) {
      continue;
    }
    int y = x;
    bool fail = false;
    for(int it = 0; it < 15; it++) {
      y = go[y];
      if(y == x) {
        fail = true;
        break;
      }
    }
    if(!fail) {
      for(int i = 0; i < 16; i++) {
        goods.push_back(x);
        x = go[x];
      }
      break;
    }
  }

  // printf("sz = %d\n", (int) goods.size());

  assert((int) goods.size() == 16);

  sort(goods.begin(), goods.end());

  vector<int> w(31, -1);
  for(int i = 0; i < (int) goods.size(); i++) {
    w[goods[i]] = i;
  }
  vector<int> d;
  for(int i = 0; i < 15; i++) {
    d.push_back(goods[i + 1] - goods[i]);
  }
  d.push_back(31 + goods[0] - goods[15]);

  vector<bool> C(31, 1);
  for(auto x : goods) {
    C[x] = 0;
  }

  vector<bool> M;

  for(int i = 0; i < 66; i++) {
    for(int j = 0; j < 31; j++) {
      if(C[j] == 0) {
        if(d[w[j]] > 0) {
          d[w[j]]--;
        }
        else {
          M.push_back(R[i][j]);
        }
      }
    }
  }

  while(M.back() == 0) {
    M.pop_back();
  }
  M.pop_back();

  return M;
}

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