Submission #1092944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092944		abczz	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	9 ms	2140 KiB

prison

#include "prison.h"
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#define ll long long

using namespace std;
vector <int> X = {2, 3, 3, 3, 3, 2, 2, 2};
vector <int> Z = {2499, 833, 277, 92, 30, 14, 6, 2};
vector <vector<int>> G = {{0}, {1, 2}, {3, 4, 5}, {6, 7, 8}, {9, 10, 11}, {12, 13, 14}, {15, 16}, {17, 18}, {19, 20}};
vector <ll> id[5001];
vector <vector<int>> F(21);

void dfs(ll u, ll l, ll r) {
  id[l].push_back(-1);
  if (l == r) return;
  id[r].push_back(-2);
  if (l+1 == r) return;
  ll sz = Z[u];
  for (int i=l+1; i<=min(r-1, l+sz); ++i) id[i].push_back(0);
  dfs(u+1, l+1, min(r-1, l+sz));
  if (l+sz >= r-1) return;
  for (int i=l+1+sz; i<=min(r-1, l+2*sz); ++i) id[i].push_back(1);
  dfs(u+1, l+1+sz, min(r-1, l+2*sz));
  if (l+2*sz >= r-1) return;
  for (int i=l+1+2*sz; i<=r-1; ++i) id[i].push_back(2);
  dfs(u+1, l+1+2*sz, r-1);
}
std::vector<std::vector<int>> devise_strategy(int N) {
  for (int i=0; i<=20; ++i) F[i].resize(N+1);
  dfs(0, 1, N);
  /*for (int i=3000; i<=3001; ++i) {
    for (auto u : id[i]) cout << u << " ";
    cout << endl;
  }*/
  ll cnt = 1;
  for (int j=0; j<=8; ++j) {
    int z = -1;
    for (auto u : G[j]) {
      ++z;
      F[u][0] = j & 1;
      for (int i=1; i<=N; ++i) {
        if (id[i].size() <= j) {
          if (id[i].back() == -1) {
            F[u][i] = (F[u][0] == 0 ? -1 : -2);
          }
          else {
            F[u][i] = (F[u][0] == 0 ? -2 : -1);
          }
          continue;
        }
        if (u && id[i][j-1] != z) {
          if (id[i][j-1] < z) F[u][i] = (F[u][0] == 0 ? -1 : -2);
          else F[u][i] = (F[u][0] == 0 ? -2 : -1);
          continue;
        }
        if (id[i][j] >= 0) {
          F[u][i] = cnt + id[i][j];
        }
        else if (id[i][j] == -1) {
          F[u][i] = (F[u][0] == 0 ? -1 : -2);
        }
        else {
          F[u][i] = (F[u][0] == 0 ? -2 : -1);
        }
      }
    }
    cnt += X[j];
  }
  /*for (int i=0; i<=20; ++i) {
    cout << i << " " << F[i][0] << " " << F[i][3000] << " " << F[i][3001] << endl;
  }*/
  return F;
}

Compilation message (stderr)

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:44:26: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |         if (id[i].size() <= j) {
      |             ~~~~~~~~~~~~~^~~~

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