제출 #659093

#제출 시각아이디문제언어결과실행 시간메모리
659093mosiashvililuka죄수들의 도전 (IOI22_prison)C++17
100 / 100
19 ms1748 KiB
#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],FX[5009],XO[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, int dep){ int i,j; //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; if(XO[rr]==1&&f[rr][0]!=bo){ cout<<"aq\n"; } XO[rr]=1; 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; if(FX[dep]==0){ FX[dep]=dp2[len]; } int qw=(len-2)/FX[dep],we=(len-2)%FX[dep]; p[0].second=q; for(j=1; j<=FX[dep]; j++){ pi++; p[j].first=p[j-1].second+1;p[j].second=p[j].first+qw-1; if(j<=we) p[j].second++; p[j].second=min(p[j].second,w-1); } 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,dep+1); break; } } } } vector<vector<int> > devise_strategy(int N) { a=N; dp[0]=0;dp[1]=dp[2]=0;//dp[3]=1; for(i=3; i<=a; i++){ dp[i]=i; for(j=2; j<=3; 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,1); /*for(i=X; i>=0; i--){ if(FX[i]!=0){ cout<<"X="<<i<<"\n"; break; } }*/ return f; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...