제출 #938375

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

prison

#include <bits/stdc++.h>
#include "prison.h"
using namespace std;
 
int cmp(int a, int b) {
  return a == b ? -1 : a > b;
}
 
vector <vector <int>> devise_strategy(int N) {
  vector <int> b = {1, 3, 3, 3, 3, 3, 3, 2, 2, 2};
  vector <int> suff(10);
  suff[9] = 1;
  for (int i = 8; i >= 0; i--)
    suff[i] = suff[i + 1] * b[i + 1];
  int ptr = 1, sofar = 0;
  vector <vector <int>> strat(23, vector <int> (N + 1));
  for (int i = 0; i < 23; i++) {
    for (; sofar < i; ptr++)
      sofar += b[ptr];
    strat[i][0] = ptr & 1;
    for (int j = 1; j <= N; j++) {
      int tmp = cmp(j / suff[ptr - 1] % b[ptr - 1], sofar - i);
      if (tmp == -1 && ptr == 9) tmp = j & 1;
      strat[i][j] = tmp == -1 ? sofar + b[ptr] - j / suff[ptr] % b[ptr] : -(tmp ^ strat[i][0]) - 1;
    }
  }
  return strat;
}

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