Submission #1136919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136919		SkillIssueWAGuy	Message (IOI24_message)	C++20	100 / 100	371 ms	852 KiB

message

#include "message.h"
#include <bits/stdc++.h>
using namespace std;

void send_message(std::vector<bool> M, std::vector<bool> C) {
  vector<vector<bool>> packets(66, vector<bool>(31, false));
  vector<int> positions, distance;
  for (int i = 0; i < 31; i++){
    if (!C[i]){
      positions.push_back(i);
    }
  }
  
  for (int i = 1; i < 16; i++){
    distance.push_back(positions[i] - positions[i-1]);
  }
  distance.push_back(positions[0] + 31 - positions[15]);
  for (int i = 0; i < 16; i++){
    for (int j = 0; j < distance[i]-1; j++){
      packets[j][positions[i]] = true;
    }
  }
  M.push_back(1);
  while (M.size() < 1025){
    M.push_back(0);
  }
  int pos = 0;
  for (int i = 0; i < 16; i++){
    for (int j = distance[i]; j < 66; j++){
      packets[j][positions[i]] = M[pos];
      pos++;
    }
  }
  for (int i = 0; i < 66; i++){
    send_packet(packets[i]);
  }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
  vector<int> connections;
  vector<int> positions;
  vector<bool> output;
  for (int i = 0; i < 31; i++){
    connections.push_back(i+1);
    int p = 0;
    while (p < 40){
      if (R[p][i]){
        connections[i]++;
        p++;
      }
      else {
        break;
      }
    }
    connections[i] %= 31;
  }
  vector<int> cache(31, -1);
  for (int i = 0; i < 31; i++){
    int cur = i;
    bool f = false;
    for (int j = 0; j < 16; j++){
      cur = connections[cur];
      if (cur == i){
        f = (j == 15);
        break;
      }
    }
    if (f){
      cur = i;
      for (int j = 0; j < 16; j++){
        positions.push_back(cur);
        cur = connections[cur];
      }
      break;
    }
  }
  for (int i = 0; i < 16; i++){
    for (int j = (connections[positions[i]] - positions[i] + 31)%31; j < 66; j++){
      output.push_back(R[j][positions[i]]);
    }
  }
  while (!output.back()){
    output.pop_back();
  }
  output.pop_back();
  return output;
}

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