Submission #1297978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297978		gesp3011v2	Message (IOI24_message)	C++20	100 / 100	424 ms	816 KiB

message

#include "message"
#include "bits/stdc++.h"
#define rep(i, n) for(int i = 0, i##__n = (int)(n); i < i##__n; ++i)
#define F(i,l,r) for(int i=l,i_end=r;i<i_end;++i)
#define FR(i,l,r) for(int i=l,i_end=r;i>=i_end;--i)
using namespace std;

vector<bool> send_packet(vector<bool> A);

void send_message(vector<bool> M, vector<bool> C) {
  vector<int> pos;
  rep(i,31) {
    if (!C[i]) {
      pos.push_back(i);
    }
  }

  vector info(66, vector<bool>(31));

  vector<int> len(31);
  rep(i,16) {
    info[(len[pos[i]] = (pos[(i + 1) % 16] - pos[i] + 31) % 31) - 1][pos[i]] = true;
  }

  int i = 0, j = 0;
  auto send = [&](bool bit) {
    while (C[j] or i < len[j]) {
      i += j == 30, j = (j + 1) % 31;
    }
    info[i][j] = bit;
    i += j == 30, j = (j + 1) % 31;
  };

 for(int i=0;i<1024-M.size();++i) {
    send(0);
  }
  send(1);
  rep(i,M.size()){
    send(M[i]);
  }

 for(auto &i : info) {
    send_packet(i);
  }
}

vector<bool> receive_message(vector<vector<bool>> R) {
  vector<int> next(31);
  rep(i,31) {
    int j = 0;
    while (j < 66 and !R[j][i]) {
      j++;
    }
    next[i] = (i + j + 1) % 31;
  }

  vector<bool> C(31, true);
  rep(i,31) {
    int len = 0, u = i;
    vector<bool> vis(31);
    while (u != next[u]) {
      if (vis[u]) {
        break;
      }
      vis[u] = true;
      len++, u = next[u];
    }
    if (len == 16 and u == i) {
      while (true) {
        C[u] = false, u = next[u];
        if (u == i) {
          break;
        }
      }
    }
  }
  
  int i = 0, j = 0;
  auto recv = [&]() {
    while (C[j] or i < (next[j] - j + 31) % 31) {
      i += j == 30, j = (j + 1) % 31;
    }
    bool ans = R[i][j];
    i += j == 30, j = (j + 1) % 31;
    return ans;
  };

  vector<bool> M;
 for(int i = 0, st = false; i < 1025; ++i) {
    bool bt = recv();
    if (st) {
      M.push_back(bt);
    }
    st |= bt;
  }
  return M;
}

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