제출 #626769

#제출 시각아이디문제언어결과실행 시간메모리
626769TheLostCookie죄수들의 도전 (IOI22_prison)C++17
0 / 100
15 ms576 KiB
#include <bits/stdc++.h> #include "prison.h" using namespace std; typedef vector<int> vi; typedef pair<int,int> ii; #define FOR(i,a,b) for(int i=(a); i<(b); ++i) #define ROF(i,a,b) for(int i=(b)-1; i>=(a); --i) #define all(v) begin(v),end(v) #define pb push_back //offline dp results //{5000, 1666, 832, 277, 92, 30, 4, 6, 2} //{0, 3, 5, 8, 11, 14, 16, 18, 20} std::vector<std::vector<int>> devise_strategy(int N) { vi layers{0, 3, 5, 8, 11, 14, 16, 18, 20}; vi splitIntoTwo{1,2,3,12,13,14,15,16,17,18}; vi splitIntoThree{0,4,5,6,7,8,9,10,11}; vector<bool> checkLeft(21); vector<vector<ii>> intervals(21); vector<vector<ii>> parInterval(21); //interval of the previous step. indexed the same way as intervals; intervals[0].pb({1,5000}); parInterval[0].pb({1,5000}); checkLeft[0] = true; FOR(i,0,19) { for(auto [l,r]: intervals[i]) { int d = r-l; int t = *next(lower_bound(all(layers),i)); if(binary_search(all(splitIntoTwo),i)) { int mid = l + (d+1)/2; intervals[t-1].pb({l+1,mid}); intervals[t].pb({mid+1,r-1}); parInterval[t-1].pb({l,r}); parInterval[t].pb({l,r}); checkLeft[t-1] = checkLeft[t] = !checkLeft[i]; } if(binary_search(all(splitIntoThree),i)) { int mid0 = l + (d+2)/3, mid1 = l + 2*((d+2)/3); intervals[t-2].pb({l+1,mid0}); intervals[t-1].pb({mid0+1,mid1}); intervals[t].pb({mid1+1,r-1}); parInterval[t-2].pb({l,r}); parInterval[t-1].pb({l,r}); parInterval[t].pb({l,r}); checkLeft[t-2] = checkLeft[t-1] = checkLeft[t] = !checkLeft[i]; } } } vector<vi> strat(21,vi(N+1)); FOR(i,0,21) { strat[i][0] = (checkLeft[i]?0:1); FOR(j,1,N+1) { int l = -1, r = 5001; FOR(k,0,int(intervals[i].size())) { if(parInterval[i][k].first <= j && j <= parInterval[i][k].second) { l = intervals[i][k].first; r = intervals[i][k].second; break; } } if(j <= l) strat[i][j] = (checkLeft[i]?-1:-2); else if(j >= r) strat[i][j] = (checkLeft[i]?-2:-1); else if(binary_search(all(splitIntoTwo),i)) { int t = *next(lower_bound(all(layers),i)); FOR(k,0,2) for(auto [f,s]: intervals[t-k]) if(f <= j && j <= s) strat[i][j] = t-k; } else if(binary_search(all(splitIntoThree),i)) { int t = *next(lower_bound(all(layers),i)); FOR(k,0,3) for(auto [f,s]: intervals[t-k]) if(f <= j && j <= s) strat[i][j] = t-k; } else { strat[i][j] = 0; //never used } assert(strat[i][j] >= -2 && strat[i][j] <= 20); } } return strat; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...