Submission #799126

#	Time	Username	Problem	Language	Result	Execution time	Memory
799126		I_Love_EliskaM_	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	13 ms	1364 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;

int A = 0;
int B = 1;
int n;

vector<vector<int>> a(21,vector<int>(5001,0));

void fill(int ind, int l, int r, int type) {

  //if (ind!=0) return;
  //if (1295-type>=l && 1295-type<=r) cout<<"Fill "<<ind<<' '<<l<<' '<<r<<' '<<type<<'\n';
  //int x; cin>>x;

  if (r-l+1==6) {

    a[ind][0]=type;
    
    a[ind][l]=-1;
    a[ind][r]=-2;
    a[ind][l+1]=a[ind][l+2]=19;
    a[ind][l+3]=a[ind][l+4]=20;

    a[19][l+1]=a[19][l]=-2; a[19][l+2]=a[19][l+3]=a[19][l+4]=a[19][r]=-1;
    a[20][l]=a[20][l+1]=a[20][l+2]=a[20][l+3]=a[20][l]=-2; a[20][l+4]=a[20][r]=-1;
    a[19][0]=a[20][0]=1;

    return;

  }

  if (r-l+1==5) {

    a[ind][0]=type;
    
    a[ind][l]=-1;
    a[ind][r]=-2;
    a[ind][l+1]=a[ind][l+2]=19;
    a[ind][l+3]=20;

    a[19][l+1]=a[19][l]=-2; a[19][l+2]=a[19][l+3]=a[19][r]=-1;
    a[20][l]=a[20][l+1]=a[20][l+2]=a[20][l]=-2; a[20][r]=-1;
    a[19][0]=a[20][0]=1;

    return;

  }

  if (r-l+1==4) {

    a[ind][0]=type;
    
    a[ind][l]=-1;
    a[ind][r]=-2;
    a[ind][l+1]=19;
    a[ind][l+2]=20;

    a[19][l]=-2; a[19][l+2]=a[19][r]=-1;
    a[20][l]=a[20][l+1]=-2; a[20][r]=-1;
    a[19][0]=a[20][0]=1;

    return;

  }

  a[ind][0]=type;
  a[ind][l]=-(type+1);
  a[((ind+2)/3+1)*3-2][l]=-((type^1)+1);
  a[((ind+2)/3+1)*3-1][l]=-((type^1)+1);
  a[((ind+2)/3+1)*3][l]=-((type^1)+1);

  a[ind][r]=-((type^1)+1);
  a[((ind+2)/3+1)*3-2][r]=-(type+1);
  a[((ind+2)/3+1)*3-1][r]=-(type+1);
  a[((ind+2)/3+1)*3][r]=-(type+1);

  int sz = (r-l+1)/3;

  for (int i=l+1; i<min(l+1+sz,n+1); ++i) a[ind][i]=((ind+2)/3+1)*3-2;
  for (int i=l+1+sz; i<min(r,n+1); ++i) a[((ind+2)/3+1)*3-2][i]=-(type+1);
  fill(((ind+2)/3+1)*3-2,l+1,l+1+sz-1,type^1);
  
  for (int i=l+1+sz; i<min(l+1+2*sz,n+1); ++i) a[ind][i]=((ind+2)/3+1)*3-1;
  for (int i=l+1; i<min(l+1+sz,n+1); ++i) a[((ind+2)/3+1)*3-1][i]=-((type^1)+1);
  for (int i=l+1+2*sz; i<min(r,n+1); ++i) a[((ind+2)/3+1)*3-1][i]=-(type+1);
  fill(((ind+2)/3+1)*3-1,l+1+sz,l+1+2*sz-1,type^1);
  
  for (int i=l+1+2*sz; i<min(r,n+1); ++i) a[ind][i]=((ind+2)/3+1)*3;
  for (int i=l+1; i<min(l+1+2*sz,n+1); ++i) a[((ind+2)/3+1)*3][i]=-((type^1)+1);
  fill(((ind+2)/3+1)*3,l+1+2*sz,r-1,type^1);

}

vector<vector<int>> devise_strategy(int _n) {
  
  n=_n;
  int sz=5000;
  a.assign(21,vector<int>(n+1,0));

  fill(0,1,5000,A);

  for (auto x:a) {
    //for (auto y:x) cout<<y<<' '; cout<<'\n';
  }
  
  return a;

}

Compilation message (stderr)

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:99:7: warning: unused variable 'sz' [-Wunused-variable]
   99 |   int sz=5000;
      |       ^~

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