Submission #1204255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204255		bynix	Message (IOI24_message)	C++20	66.34 / 100	433 ms	852 KiB

message

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

void send_message(vb M, vb C){
  bool short_message = (M.size() != 1024);

  vector<int> id(16, 0); int c = 0;
  for (int i = 0; i < 31; i++) if (!C[i]) id[c] = i, c++;
  
  vb ones(31, 1), zeroes(31, 0);
  map<int, vb> m = {{0, zeroes}, {1, ones}};
  for (int i = 0; i < 5; i++) send_packet(m[(id[0] >> i) & 1]);

  for (int i = 0; i < 5; i++){
    vb packet(31, 0);
    for (int j = 0; j < 15; j++) packet[id[j]] = (id[j + 1] >> i) & 1;
    if (i == 0) packet[id[15]] = short_message;
    send_packet(packet);
  }

  if (short_message){
    int l = M.size();
    M.push_back(1);
    for (int i = 0; i < 1024 - l; i++) M.push_back(0);
  }

  for (int i = 0; i < 1024; i += 16){
    vb packet(31, 0);
    for (int j = i; j < i + 16; j++) packet[id[j - i]] = M[j];
    send_packet(packet);
  }
}

vb receive_message(vector<vb> R){
  vector<int> id(16, 0);
  for (int i = 0; i < 5; i++){
    int o = 0;
    for (int j = 0; j < 31; j++) o += R[i][j];
    id[0] |= ((o > 15) << i);
  }

  for (int j = 1; j < 16; j++) for (int k = 0; k < 5; k++) id[j] |= (R[k + 5][id[j - 1]] <<  k);
  bool short_message = R[5][id[15]];
  
  vb M(1024, 0);
  int l = 0;
  for (int i = 0; i < 64; i++)
    for (int j = 0; j < 16; j++){
      M[i*16 + j] = R[i + 10][id[j]];
      l = M[i*16 + j] ? (i*16 + j) : l;
    }

  if (short_message) {
    vb M2(l, 0);
    for (int i = 0; i < l; i++) M2[i] = M[i];
    return M2;
  } else return M;
}

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