Submission #1191687

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

message

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


using namespace std;



void send_message(vector<bool> M, vector<bool> C) {
  vector<int> P(31, 0);
  int j = 0, k = 0;
  while (C[j]) j++;
  bool flag = false;
  for (int i = j; ; i++){
    i %= 31;
    if (i == j){
      if (flag){
        break;
      }
      flag = true;
    }
    if (C[i] == 0)
      k = i;
    else
      P[k]++;
  }
  vector<bool> A(31, 0);
  for (int b = 0; b < 4; b++){
    for (int i = 0; i < 31; i++){
      A[i] = P[i] % (1LL << (b + 1)) >= (1LL << b);
    }
    send_packet(A);
  }
  for (int i = 0; i < (M.size() - 1) / 16 + 1; i++){
    k = 0;
    for (int j = 0; j < 31; j++){
      if (C[j] == 0){
        A[j] = M[i * 16 + k];
        k++;
        if (i * 16 + k == M.size())
        break;
      }
    }
    send_packet(A);
  }
  k = 0;
  for (int j = 0; j < 31; j++){
    if (C[j] == 0){
      if (M.size() % 16)
      A[j] = M.size() % 16 > k;
      else
      A[j] = 1;
      k++;
    }
  }
  send_packet(A);
}

vector<bool> receive_message(vector<vector<bool>> R) {
  vector<int> P(31, 0);
  for (int i = 0; i < 31; i++){
    P[i] = R[0][i] + R[1][i] * 2 + R[2][i] * 4 + R[3][i] * 8;
  }
  vector<int> vis(31);
  vector<int> C(31);
  for (int i = 0; i < 31; i++){
    int cnt = 1;
    int j = i;
    while (vis[j] == 0){
      vis[j] = cnt;
      cnt++;
      j = j + P[j] + 1;
      j %= 31;
    }
    if (cnt - vis[j] == 16){
      while (vis[j] != INT_MAX){
        vis[j] = INT_MAX;
        C[j] = true;
        j = j + P[j] + 1;
        j %= 31;
      }
    }else{
      while (vis[j] != INT_MAX){
        vis[j] = INT_MAX;
        j = j + P[j] + 1;
        j %= 31;
      }
    }
  }
  vector<bool> ret;
  for (int i = 4; i < R.size() - 1; i++){
    for (int j = 0; j < 31; j++){
      if (C[j])
        ret.push_back(R[i][j]);
    }
  }
  for (int j = 0; j < 31; j++){
    if (C[j] && R[R.size() - 1][j] == 0)
      ret.pop_back();
  }
  return ret;
}

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