Submission #755103

#	Time	Username	Problem	Language	Result	Execution time	Memory
755103		Piokemon	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	5 ms	980 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int pot[15];
vector<vector<int>> odp;

void zrob(int x, int l, int r, int nr){
  if (r-l==1){
    odp[x][l] = (odp[x][0]==0?-1:-2);
    odp[x][r] = (odp[x][0]==0?-2:-1);
    return;
  }
  if (r-l==2){
    odp[x][l] = (odp[x][0]==0?-1:-2);
    odp[x][l+1] = 3*nr+1;
    odp[3*nr+1][0] = 1-odp[x][0];
    odp[3*nr+1][l] = (odp[3*nr+1][0]==0?-1:-2); odp[3*nr+1][r] = (odp[3*nr+1][0]==0?-2:-1);
    odp[x][r] = (odp[x][0]==0?-2:-1);
    return;
  }
  if (l>r) return;
  odp[3*nr+1][0] = 1-odp[x][0]; odp[3*nr+2][0] = 1-odp[x][0]; odp[3*nr+3][0] = 1-odp[x][0];

  for (int y=l+1;y<l + (r-l)/3;y++) odp[x][y] = 3*nr+1;
  for (int y=l + (r-l)/3;y<=r;y++) odp[3*nr+1][y] = (odp[3*nr+1][0]==0?-2:-1);
  odp[3*nr+1][l] = (odp[3*nr+2][0]==0?-1:-2);
  zrob(3*nr+1,l+1,l + (r-l)/3-1,nr+1);

  for (int y=l+(r-l)/3;y<l + 2*(r-l)/3;y++) odp[x][y] = 3*nr+2;
  for (int y=l;y<l+(r-l)/3;y++) odp[3*nr+2][y] = (odp[3*nr+2][0]==0?-1:-2);
  for (int y=l + 2*(r-l)/3;y<=r;y++) odp[3*nr+2][y] = (odp[3*nr+2][0]==0?-2:-1);
  zrob(3*nr+2,l+(r-l)/3+1,l + 2*(r-l)/3-1,nr+1);

  for (int y=l + 2*(r-l)/3;y<r;y++) odp[x][y] = 3*nr+3;
  for (int y=l;y<l + 2*(r-l)/3;y++) odp[x][y] = (odp[3*nr+2][0]==0?-1:-2);
  odp[3*nr+3][r] = (odp[3*nr+2][0]==0?-2:-1);
  zrob(3*nr+3,l + 2*(r-l)/3+1,r-1,nr+1);
}

vector<vector<int>> devise_strategy(int N) {
  vector<int> czesc (N+1,0);
  vector<vector<int>> cos (23,czesc);
  odp = cos;
  zrob(0,1,N,0);
  /*for (int x=0;x<23;x++){
    for (int y=0;y<=N;y++){
      cout << odp[x][y] << ' ';
    }
    cout << '\n';
  }*/
  return odp;
}

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