Submission #1195395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195395		aykhn	Message (IOI24_message)	C++20	100 / 100	390 ms	856 KiB

message

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

using namespace std;

void send_message(vector<bool> M, vector<bool> C) 
{
  vector<int> idx;
  for (int i = 0; i < 31; i++) 
  {
    if (C[i] == 0) idx.push_back(i);
  }
  vector<vector<bool>> R(66, vector<bool>(31, 0));
  vector<bool> real;
  for (int i = 0; i < 1025 - (int)M.size() - 1; i++) real.push_back(0);
  real.push_back(1);
  for (int i = 0; i < M.size(); i++) real.push_back(M[i]);
  idx.push_back(31 + idx[0]);
  int nxt[31];
  for (int i = 0; i < 16; i++)
  {
    int val = idx[i + 1] - idx[i];
    nxt[idx[i]] = idx[i + 1];
    R[val - 1][idx[i]] = 1;
  }
  for (int i = 0, cur = 0; i < 66; i++)
  {
    for (int j = 0; j < 31; j++)
    {
      if (C[j] == 1) continue;
      if (nxt[j] - j > i) continue;
      if (cur < 1025) R[i][j] = real[cur++];
    }
  }
  for (int i = 0; i < 66; i++) send_packet(R[i]);
}
vector<int> adj[31];
int used[31], par[31];
vector<int> cyc;

int dfs(int a)
{
  used[a] = 1;
  for (int &v : adj[a])
  {
    if (used[v] == 2) continue;
    if (used[v] == 1)
    {
      int x = a;
      while (1)
      {
        cyc.push_back(x);
        if (x == v) break;
        x = par[x];
      }
      used[a] = 2;
      return 1;
    }
    par[v] = a;
    if (dfs(v)) 
    {
      used[a] = 2;
      return 1;
    }
  }
  used[a] = 2;
  return 0;
}

vector<bool> receive_message(vector<vector<bool>> R) 
{
  for (int i = 0; i < 31; i++) adj[i].clear(), used[i] = 0, par[i] = 0;
  vector<bool> res;
  int val[31];
  for (int i = 0; i < 31; i++)
  {
    int j = 0;
    while (j < 66 && R[j][i] == 0) j++;
    val[i] = j;
    adj[i].push_back((i + j + 1) % 31);
  }
  vector<int> idx;
  for (int i = 0; i < 31; i++)
  {
    if (!used[i]) 
    {
      cyc.clear();
      dfs(i);
      if (cyc.size() > idx.size()) idx = cyc;
    }
  }
  sort(idx.begin(), idx.end());
  vector<int> ok(31, 0);
  for (int i : idx) ok[i] = 1;
  for (int i = 0; i < 66; i++)
  {
    for (int j = 0; j < 31; j++)
    {
      if (!ok[j]) continue;
      if (val[j] >= i) continue;
      if (res.size() < 1025) res.push_back(R[i][j]);
    }
  }
  vector<bool> real;
  int i = 0;
  while (i < res.size() && res[i] == 0) i++;
  for (i++; i < res.size(); i++) real.push_back(res[i]);
  return real;
}

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