Submission #1203907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203907		abczz	Message (IOI24_message)	C++20	100 / 100	404 ms	880 KiB

message

#include "message.h"
#include <iostream>
#include <vector>
#include <queue>
#define ll long long

using namespace std;

vector <ll> V;
ll S[66][31], cur[31];
void send_message(std::vector<bool> M, std::vector<bool> C) {
  V.clear();
  for (int i=0; i<31; ++i) {
    cur[i] = 0;
    if (C[i] == 0) V.push_back(i);
  }
  for (int i=0; i<V.size(); ++i) {
    for (int j=0; j<(i == V.size()-1 ? V[0]+31 : V[i+1])-V[i]-1; ++j) {
      S[cur[V[i]]++][V[i]] = 0;
    }
    S[cur[V[i]]++][V[i]] = 1;
  }
  for (auto u : M) {
    for (auto v : V) {
      if (cur[v] == 66) continue;
      S[cur[v]++][v] = u;
      break;
    }
  }
  auto z = M.back();
  while (true) {
    bool ok = 0;
    for (auto v : V) {
      if (cur[v] == 66) continue;
      ok = 1;
      S[cur[v]++][v] = z ^ 1;
      break;
    }
    if (!ok) break;
  }
  for (int i=0; i<66; ++i) {
    vector <bool> Q;
    for (int j=0; j<31; ++j) Q.push_back((bool)S[i][j]);
    send_packet(Q);
  }
}

vector <ll> adj[31];
bool visited[31];
void dfs(ll u) {
  visited[u] = 1;
  for (auto v : adj[u]) {
    if (!visited[v]) dfs(v);
  }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
  ll cur[31];
  for (int i=0; i<31; ++i) {
    adj[i].clear();
    cur[i] = 0;
    for (int j=0; j<66; ++j) {
      ++cur[i];
      if (R[j][i] == 1) {
        adj[i].push_back((i+j+1) % 31);
        break;
      }
    }
  }
  vector <ll> X;
  for (int i=0; i<31; ++i) {
    for (int j=0; j<31; ++j) visited[j] = 0;
    dfs(i);
    ll f = 0;
    for (int j=0; j<31; ++j) f += (ll)visited[j];
    if (f == 16) X.push_back(i);
  }
  vector <bool> M;
  for (auto u : X) {
    for (int i=cur[u]; i<66; ++i) {
      M.push_back(R[i][u]);
    }
  }
  while (!M.empty()) {
    auto u = M.back();
    M.pop_back();
    if (M.back() != u) break;
  }
  return M;
}

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