제출 #1217711

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1217711		nikd	메시지 (IOI24_message)	C++20	100 / 100	389 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>> to_send(66, vector<bool>(31, 0));
  vector<int> idx;
  
  for(int i = 0; i<31; i++) if(!C[i]) idx.push_back(i);
  
  vector<int> diff(16);
  for(int i = 0; i<15; i++){
    int dst = idx[i+1]-idx[i];
    diff[i] = dst;
    to_send[dst-1][idx[i]] = 1;
  }
  int dst = idx[0]-idx[15]+31;
  diff[15] = dst;
  to_send[dst-1][idx[15]] = 1;
  
  vector<bool> m(1025, 0);
  for(int j = 0; j<M.size(); j++) m[j] = M[j];
  m[M.size()] = 1;
  
  int cnt = 0;
  for(int i = 0; i<66; i++){
    for(int j = 0; j<16; j++){
      if(i>=diff[j]) to_send[i][idx[j]] = m[cnt++];  
    }
  }
  for(int i = 0; i<66; i++) send_packet(to_send[i]);
  // for(int i = 0; i<66; i++){
  //   for(int j = 0; j<31; j++) cerr << to_send[i][j] << ' ';
  //   cerr << '\n';
  // }
  return;
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
  vector<int> idx;

  auto get_next = [&R](int curr)->int{
    int tt = 0;
    while(tt<16 && !R[tt][curr]) tt++;
    if(tt>=16) return -1;
    return (curr+tt+1)%31; 
  };

  for(int ii = 0; ii<16; ii++){
    vector<bool> vis(31, 0);
    int i = ii;
    vis[i] = 1;
    for(int j = 0; j<15; j++){
      i = get_next(i);
      // cerr << i << ' ';
      if(i==-1) break;
      if(vis[i]){
        i = -1; break;
      }
      vis[i] = 1;
    }
    if(i == -1) continue;
    i = get_next(i);
    if(i==-1) continue;
    if(i != ii) continue;
    for(int tt = 0; tt<31; tt++) if(vis[tt]) idx.push_back(tt);
    break;
  }

  assert(idx.size()==16);
  vector<int> diff(16);
  for(int i = 0; i<15; i++) diff[i] = idx[i+1]-idx[i];
  diff[15] = idx[0]-idx[15]+31;

  vector<bool> received;
  for(int i = 0; i<R.size(); i++){
    for(int j = 0; j<16; j++){
      if(i<diff[j]) continue;
      received.push_back(R[i][idx[j]]);
    }
  }
  
  int sz;
  for(sz = 1024; !received[sz]; sz--);
  vector<bool> sol(sz);
  for(int i = 0; i<sz; i++) sol[i] = received[i];
  return sol;
}

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