제출 #979460

#제출 시각아이디문제언어결과실행 시간메모리
97946012345678죄수들의 도전 (IOI22_prison)C++17
100 / 100
9 ms1372 KiB
#include "prison.h" #include <bits/stdc++.h> using namespace std; const int nx=5105, kx=21; int di[]={3, 3, 3, 3, 3, 3, 2}, cnt, qs[kx]; vector<vector<int>> ans(kx, vector<int> (nx+1)); vector<pair<int, int>> d[kx]; void solve(int l, int r, int layer, int nextlayer, int cur) { d[cur].push_back({l, r}); if (r==l+1) return; l++, r--; int dif=(r-l+1)/di[layer], x=l; for (int i=0; i<di[layer]; i++) solve(x, x+dif-1, layer+1, nextlayer+di[layer], nextlayer+i), x=x+dif; } std::vector<std::vector<int>> devise_strategy(int N) { solve(1, 5102, 0, 1, 0); ans[0][1]=-1; ans[0][5102]=-2; for (int i=2; i<=5101; i++) ans[0][i]=(i-2)/1700+1; for (int i=1; i<=7; i++) qs[i]=qs[i-1]+di[i-1]; for (int i=0; i<7; i++) { for (int j=1; j<=di[i]; j++) { ans[qs[i]+j][0]=1-(i%2); for (auto x:d[qs[i]+j]) { ans[qs[i]+j][x.first]=(i%2)?-1:-2; ans[qs[i]+j][x.second]=(i%2)?-2:-1; if (x.first+1==x.second) continue; int sz=(x.second-x.first-1)/di[i+1]; for (int k=x.first+1; k<x.second; k++) ans[qs[i]+j][k]=((k-x.first-1)/sz)+1+qs[i+1]; } if (i==0) { for (int k=1; ; k++) { if (ans[qs[i]+j][k]) break; ans[qs[i]+j][k]=(i%2)?-1:-2; } for (int k=5102; ; k--) { if (ans[qs[i]+j][k]) break; ans[qs[i]+j][k]=(i%2)?-2:-1; } } else { for (int m=1; m<=di[i-1]; m++) { for (auto r:d[qs[i-1]+m]) { int vl=(i%2)?-1:-2; for (int k=r.first; k<=r.second; k++) { if (ans[qs[i]+j][k]) vl=(i%2)?-2:-1; else ans[qs[i]+j][k]=vl; } } } } } } vector<vector<int>> res(kx, vector<int> (N+1)); for (int i=0; i<kx; i++) for (int j=0; j<=N; j++) res[i][j]=ans[i][j]; return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...