# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
858730 | kim | Prisoner Challenge (IOI22_prison) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "prison.h"
#include<bits/stdc++.h>
using namespace std;
//#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define int ll
vector<vector<int>> devise_strategy(int N){
vector<vector<int>> ans(61);
vector<int> vec(N+1);
vec[0]=0;
for(int i=1;i<=N/2;++i) vec[i]=1;
for(int i=N/2+1;i<=N;++i) vec[i]=2;
ans[0]=vec;
int n=1;
for(int x=1,y=2,z=N/2;y<=60&&z>=1;x+=2,y+=2,z>>=1){
vec[0]=((y/2)%2);
int t=(1<<(x/2));
int now=0;
for(int k=0;k<t;++k){
for(int i=1;i<=z/2;++i) vec[i+now]=x+2;
for(int i=z/2+1;i<=z;++i) vec[i+now]=y+2;
for(int i=z+1;i<=z+z;++i) vec[i+now]=-(1-vec[0])-1;
now+=z+z;
}
// if(vec[0]==0) vec[1]=-1;
// else vec[1]=-2;
ans[x]=vec;
now=0;
for(int k=0;k<t;++k){
for(int i=1;i<=z;++i) vec[i+now]=-(vec[0])-1;
for(int i=z+1;i<=z+z/2;++i) vec[i+now]=x+2;
for(int i=z+z/2+1;i<=z+z;++i) vec[i+now]=y+2;
now+=z+z;
}
// if(vec[0]==0) vec[1]=-1;
// else vec[1]=-2;
ans[y]=vec;
n+=2;
}
// cout<<n<<endl;
ans.resize(n);
return ans;
}