제출 #834864

#제출 시각아이디문제언어결과실행 시간메모리
834864gagik_2007죄수들의 도전 (IOI22_prison)C++17
44 / 100
15 ms1492 KiB
#include "prison.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define ff first #define ss second ll ttt; const ll INF=1e18; const ll MOD=1e9+7; const ll N=5007; ll n,m,k; ll pw[N]; int ind=0; void comp_result(vector<vector<int>>&ans, int cur){ // cur = (k+1)*step+rem // rem=0 -> A // rem!=0 -> B, A_(rem-1) int mnac=cur%(k+1); if(mnac==0){ ans[cur][0]=0; } else{ ans[cur][0]=1; // mnac-1 -> the group of the bag A } int tmp=cur; cur/=(k+1); // the current step (k^(ind-cur)) // ind-cur>=1 (don't need more), => cur<=ind-1 => num<=(k+1)*(ind-1) for(int i=1;i<=n;i++){ int vl=i; vl%=pw[ind-cur+1]; vl/=pw[ind-cur]; if(mnac!=0){ if(vl<mnac-1){ ans[tmp][i]=-2; } else if(vl>mnac-1){ ans[tmp][i]=-1; } else{ ans[tmp][i]=(k+1)*(cur+1); } } else{ int res=(k+1)*cur+vl+1; ans[tmp][i]=res; } // cout<<ans[tmp][i]<<" "; if(ans[tmp][i]==(k+1)*(ind+1))ans[tmp][i]=0; // if(ans[tmp][i]>(k+1)*(ind+1))cout<<tmp<<" "<<i<<": "<<ans[tmp][i]<<endl; } // cout<<endl; } vector<vector<int>> devise_strategy(int NN) { n=NN; k=4; pw[0]=1; while(pw[ind]<=n){ ind++; pw[ind]=pw[ind-1]*k; } ind--; // cout<<ind<<endl; vector<vector<int>>ans((k+1)*(ind+1),vector<int>(n+1,0)); for(int i=0;i<(k+1)*(ind+1);i++){ comp_result(ans,i); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...