# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
858738 | 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
const int md=1e9+7;
const int inf=1e9+7;
vector<vector<int>> devise_strategy(int N){
// int kk;
// for(kk=1;kk<N;kk<<=1);
N=512;
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;
}
int32_t main(){
ios::sync_with_stdio(false); cin.tie(0);
vector<vector<int>> ans;
int n; cin>>n;
ans=devise_strategy(n);
cout<<"[\n";
for(auto &e:ans){
cout<<"[";
for(auto &f:e) cout<<f<<" ";
cout<<"]\n";
}
cout<<"]";
return 0;
}
/**
*/