Submission #755219

#	Time	Username	Problem	Language	Result	Execution time	Memory
755219		Piokemon	Prisoner Challenge (IOI22_prison)	C++17	60 / 100	16 ms	2192 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int pot[15];
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 (l==r){
    odp[3*nr+1][0] = 1-odp[x][0];
    odp[x][l] = 3*nr+1;
    odp[3*nr+1][l-1] = (odp[3*nr+1][0]==0?-1:-2);
    if (r+1 <= n) odp[3*nr+1][r+1] = (odp[3*nr+1][0]==0?-2:-1);
    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;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,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});
}

vector<vector<int>> devise_strategy(int N) {
  vector<int> czesc (N+1,0);
  vector<vector<int>> cos (26,czesc);
  odp = cos;
  n = N;
  odp[0][0] = 0;
  zrob(0,1,6560,0,{1,6560});
  /*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: 50 / 90