Submission #836154

#	Time	Username	Problem	Language	Result	Execution time	Memory
836154		becaido	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	9 ms	980 KiB

prison

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "prison.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() { cout << "\n"; }
template<typename T, typename...U>
void dout(T t, U...u) { cout << t << (sizeof...(u) ? ", " : ""), dout(u...); }
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for(int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

vector<vector<int>> devise_strategy(int N) {
    vector<vector<int>> ans;
    auto rec = [&](auto rec, int pos, int rp, int l, int r, int L, int R, int len, bool is)->void {
        while (pos >= ans.size()) ans.pb(vector<int>(N + 1, 0));
        ans[pos][0] = is;
        FOR (i, L, l) ans[pos][i] = (is == 0 ? -1 : -2);
        FOR (i, r, R) ans[pos][i] = (is == 0 ? -2 : -1);
        if (l + 1 > r - 1) return;
        len -= 2;
        int k = min(len, (len > 4 ? 3 : 2)), x = (r - l - 1 + k - 1) / k;
        for (int i = l + 1, j, cnt = 1; i < r; i = j + 1, cnt++) {
            j = min(r - 1, i + x - 1);
            FOR (p, i, j) ans[pos][p] = rp + cnt;
            rec(rec, rp + cnt, rp + k, i, j, l, r, (len + k - 1) / k, !is);
        }
    };
    rec(rec, 0, 0, 1, N, 1, N, N, 0);
    return ans;
}

/*
in1
3
1 2
1 3
2 1
2 3
3 1
3 2
-1
out1
A
A
B
A
B
B
*/

#ifdef WAIMAI
static constexpr int kNumPrisoners = 500;

static void invalid_strategy(string message) {
  printf("%s\n", message.c_str());
  exit(0);
}

int main() {
  int N;
  assert(1 == scanf("%d", &N));

  vector<vector<int>> strategy = devise_strategy(N);
  if (strategy.size() == 0) {
    invalid_strategy("s is an empty array");
  }
  int x = strategy.size() - 1;
  for (int i = 0; i <= x; ++i) {
    if (static_cast<int>(strategy[i].size()) != N + 1) {
      invalid_strategy("s[i] contains incorrect length");
    }
    if (strategy[i][0] < 0 || strategy[i][0] > 1) {
      invalid_strategy("First element of s[i] is non-binary");
    }
    for (int j = 1; j <= N; ++j) {
      if (strategy[i][j] < -2 || strategy[i][j] > x) {
        invalid_strategy("s[i][j] contains incorrect value");
      }
    }
  }

  int A, B;
  while (1 == scanf("%d", &A) && A != -1) {
    assert(1 == scanf("%d", &B));
    bool answer = false;
    int whiteboard = 0;
    for (int i = 0; i < kNumPrisoners && !answer; ++i) {
      int check = strategy[whiteboard][0];
      whiteboard = strategy[whiteboard][check == 0 ? A : B];
      if (whiteboard < 0) {
        answer = true;
        printf("%c\n", "BA"[whiteboard + 2]);
      }
    }
    if (!answer) {
      printf("X\n");
    }
  }
}
#endif

Compilation message (stderr)

prison.cpp: In instantiation of 'devise_strategy(int)::<lambda(auto:23, int, int, int, int, int, int, int, bool)> [with auto:23 = devise_strategy(int)::<lambda(auto:23, int, int, int, int, int, int, int, bool)>]':
prison.cpp:42:36:   required from here
prison.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         while (pos >= ans.size()) ans.pb(vector<int>(N + 1, 0));
      |                ~~~~^~~~~~~~~~~~~

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