Submission #300190

#	Time	Username	Problem	Language	Result	Execution time	Memory
300190		model_code	Painting Squares (IOI20_squares)	C++17	100 / 100	146 ms	752 KiB

squares

// william-ac
#include "squares.h"
#include <vector>

std::vector<int> labels, visited, euler_path;
int reverse_map[1024];

void dfs(int x) {
  while (visited[x] < 2) {
    dfs((x >> 1) | (visited[x]++ << 8));
  }
  euler_path.push_back(x);
}

void generate_map() {
  visited.assign(512, 0);
  euler_path.clear();
  dfs(0);
  labels.clear();
  labels.assign(8, 0);
  for (int i = 0; i < (int)euler_path.size() - 1; i++) {
    labels.push_back(euler_path[i] & 1);
    reverse_map[(euler_path[i] << 1) | (euler_path[i + 1] & 1)] = i;
  }
}

std::vector<int> paint(int n) {
  if (euler_path.empty()) {
    generate_map();
  }
  std::vector<int> painting(n + 1);
  for (int i = 0; i < n; i++) {
    painting[i] = labels[i];
  }
  painting[n] = 10;
  return painting;
}

int find_location(int n, std::vector<int> c) {
  if (euler_path.empty()) {
    generate_map();
  }
  int val = 0;
  for (int i = 0; i < (int)c.size(); i++) {
    if (c[i] == -1) return n - i;
    val = (val << 1) | c[i];
  }
  return reverse_map[val];
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55