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<bits/stdc++.h>
#include "prison.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,dp[5009],dp2[5009];
vector <vector <int> > f;
map <vector <int>, bool> mp;
void rec(int q, int w, int rr, int l, int r, bool bo, int cnt){
//cout<<q<<" "<<w<<" "<<rr<<" "<<l<<" "<<r<<" "<<bo<<" "<<cnt<<endl;
vector <int> V;
V.push_back(q);V.push_back(w);V.push_back(rr);V.push_back(l);V.push_back(r);V.push_back(bo);V.push_back(cnt);
if(mp[V]==1) return;
mp[V]=1;
int i,j;
f[rr][0]=bo;
//
for(i=l; i<=r; i++){
if(i<q){
//esaa patara(bo)
if(bo==0) f[rr][i]=-1; else f[rr][i]=-2;
continue;
}
if(i>w){
//isaa patara
if(bo==0) f[rr][i]=-2; else f[rr][i]=-1;
continue;
}
if(i==q){
//esaa patara
if(bo==0) f[rr][i]=-1; else f[rr][i]=-2;
continue;
}
if(i==w){
//isaa patara
if(bo==0) f[rr][i]=-2; else f[rr][i]=-1;
continue;
}
if(w-q+1==3){
f[rr][i]=cnt+1;
rec(q+1,w-1,cnt+1,q,w,!bo,cnt+1);
continue;
}
pair <int, int> p[5];int pi=0;
int len=w-q+1;
int qw=(len-2)/dp2[len],we=(len-2)%dp2[len];
p[0].second=q;
for(j=1; j<=dp2[len]; j++){
pi++;
p[j].first=p[j-1].second+1;p[j].second=p[j].first+qw-1;
if(j<=we) p[j].second++;
}
for(j=1; j<=pi; j++){
if(p[j].first<=i&&i<=p[j].second){
f[rr][i]=cnt+j;
rec(p[j].first,p[j].second,cnt+j,q,w,!bo,cnt+pi);
break;
}
}
}
}
vector<vector<int> > devise_strategy(int N) {
a=N;
dp[0]=0;dp[1]=dp[2]=0;dp[3]=1;
for(i=4; i<=a; i++){
dp[i]=i;
for(j=2; j<=2; j++){
c=(i-2)/j;
if((i-2)%j!=0) c++;
if(dp[i]>dp[c]+j){
dp[i]=dp[c]+j;dp2[i]=j;
}
}
}
int X=dp[a]+1;
f.resize(X);
for(i=0; i<X; i++){
f[i].resize(a+1);
}
rec(1,a,0,1,a,0,0);
return f;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |