제출 #659066

#제출 시각아이디문제언어결과실행 시간메모리
659066mosiashvililuka죄수들의 도전 (IOI22_prison)C++17
10 / 100
20 ms1420 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]; 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<=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); return f; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...