Submission #755266

#	Time	Username	Problem	Language	Result	Execution time	Memory
755266		Piokemon	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	13 ms	1788 KiB

prison

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

void zrob(int x, int l, int r, int nr, pair<int,int> poprz){
  if (l>n) return;
  for (int y=poprz.first;y<=l && y<=n;y++) odp[x][y] = (odp[x][0]==0?-1:-2);
  for (int y=r;y<=poprz.second && y<=n;y++) odp[x][y] = (odp[x][0]==0?-2:-1);
  l++; r--;
  if (l>=r) return;
  if (nr<6){
    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;y<l+(r-l+1)/3 && y<=n;y++) odp[x][y] = 3*nr+1;
    zrob(3*nr+1,l,l+(r-l+1)/3 - 1,nr+1,{l-1,r+1});

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

    for (int y=l+2*(r-l+1)/3;y<=r && y<=n;y++) odp[x][y] = 3*nr+3;
    zrob(3*nr+3,l+2*(r-l+1)/3,r,nr+1,{l-1,r+1});
  }
  else{
    odp[7+2*nr][0] = 1-odp[x][0]; odp[7+2*nr+1][0] = 1-odp[x][0];

    for (int y=l;y<l+(r-l+1)/2 && y<=n;y++) odp[x][y] = 7+2*nr;
    zrob(7+2*nr,l,l+(r-l+1)/2-1,nr+1,{l-1,r+1});

    for (int y=l+(r-l+1)/2;y<=r && y<=n;y++) odp[x][y] = 7+2*nr+1;
    zrob(7+2*nr+1,l+(r-l+1)/2,r,nr+1,{l-1,r+1});
  }
}

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

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