제출 #814031

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
814031		KoD	죄수들의 도전 (IOI22_prison)	C++17	80 / 100	10 ms	1076 KiB

prison

#include "prison.h"

#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

using std::array;
using std::pair;
using std::string;
using std::tuple;
using std::vector;

using std::begin;
using std::end;

using ll = long long;
constexpr int inf = (1 << 30) - 1;
constexpr ll infll = (1ll << 62) - 1;

vector<vector<int>> devise_strategy(int N) {
  const int D = 8;
  const int M = 22;
  vector pow3(D, 1);
  for (int i = 1; i < D; ++i) {
    pow3[i] = pow3[i - 1] * 3;
  }
  const auto get = [&](int i, int d) {
    return (i / pow3[d]) % 3;
  };
  vector S(M + 1, vector(N + 1, 0));
  {
    S[0][0] = 0;
    for (int i = 1; i <= N; ++i) {
      S[0][i] = (D - 1) * 3 - 1 + get(i, D - 1);
    }
  }
  {
    S[1][0] = 0;
    for (int i = 1; i <= N; ++i) {
      S[1][i] = (i % 3 == 0) ? -1 : -2;
    }
  }
  for (int d = D - 1; d >= 1; --d) {
    const int type = (D - d) & 1;
    for (int r = 0; r <= 2; ++r) {
      const int u = d * 3 - 1 + r;
      S[u][0] = type;
      for (int i = 1; i <= N; ++i) {
        const int k = get(i, d);
        if (r == k) {
          const int k2 = get(i, d - 1);
          if (d == 1) {
            if (k2 == 1) {
              S[u][i] = 1;
            } else {
              S[u][i] = ((k2 == 0) xor type) ? -1 : -2;
            }
          } else {
            S[u][i] = (d - 1) * 3 - 1 + k2;
          }
        } else {
          S[u][i] = ((r > k) xor type) ? -1 : -2;
        }
      }
    }
  }
  return S;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 70 / 90