Submission #932419

#	Time	Username	Problem	Language	Result	Execution time	Memory
932419		nguyentunglam	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	9 ms	1372 KiB

prison

#include<bits/stdc++.h>
#include "prison.h"

#include <vector>

using namespace std;

const int N = 6000;

int a[N][10];

int f[30], g[30], bit[30];

int val_bit[30], point[30], pos_bit[30][30];

std::vector<std::vector<int>> devise_strategy(int N) {
  f[0] = 2;
  for(int i = 1; i <= 20; i++) {
    for(int j = 1; j <= i; j++) {
      if (f[i] < f[i - j] * j + 2) {
        f[i] = f[i - j] * j + 2;
        g[i] = j;
      }
    }
  }

  int x = 20, cnt = 0;
  while (x) {
    bit[++cnt] = g[x];
    x -= g[x];
  }

  int n = f[20];

  for(int i = 1; i <= n; i++) {
    int val = i, l = 1, r = n;
    for(int j = 1; j <= cnt + 1; j++) {
      if (i == l) {
        a[i][j] = -1;
        break;
      }
      if (i == r) {
        a[i][j] = 100;
        break;
      }
      l++; r--;
      int ok = (r - l + 1) % bit[j];
      assert(ok == 0);
      int diff = (r - l + 1) / bit[j];
      for(int k = 1; k < bit[j]; k++) {
        if (l + k * diff <= i) a[i][j] = k;
      }
      int pre = l;
      l = pre + a[i][j] * diff;
      r = pre + (a[i][j] + 1) * diff - 1;
    }
  }

  vector<vector<int> > s(21, vector<int> (N + 1, 0));

  for(int i = 1, p = 0, cur = 1; i <= cnt; i++) {
    for(int j = 0; j < bit[i]; j++) {
      s[++p][0] = cur;
      val_bit[p] = j;
      pos_bit[i][j] = p;
      point[p] = i;
    }
    cur ^= 1;
  }

  auto guess = [&] (int st) {
    if (st == 0) return -1;
    return -2;
  };

  for(int i = 0; i <= 20; i++) {
    for(int j = 1; j <= N; j++) {
      int x = val_bit[i];
      int y = a[j][point[i]];
      if (x != y && i) {
        int z = x < y ? s[i][0] ^ 1 : s[i][0];
        s[i][j] = guess(z);
      }
      else {
        int send = a[j][point[i] + 1];
        if (send < 0) s[i][j] = guess(s[i][0]);
        else if (send == 100) s[i][j] = guess(s[i][0] ^ 1);
        else s[i][j] = pos_bit[point[i] + 1][send];
      }
    }
  }

  return s;
}

Compilation message (stderr)

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:36:9: warning: unused variable 'val' [-Wunused-variable]
   36 |     int val = i, l = 1, r = n;
      |         ^~~

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