제출 #628726

#제출 시각아이디문제언어결과실행 시간메모리
628726tutis죄수들의 도전 (IOI22_prison)C++17
54.50 / 100
22 ms1216 KiB
#include "prison.h" #include <bits/stdc++.h> using namespace std; std::vector<std::vector<int>> devise_strategy(int N) { vector<vector<int>>ret; vector<pair<int, int>>S = {{1, N}}; vector<pair<int, int>>S_; while (!S.empty()) { S_ = {}; int x = (int)ret.size(); int mx = 0; for (int i = 0; i < (int)S.size(); i++) { int lo = S[i].first; int hi = S[i].second; lo++; hi--; mx = max(mx, hi - lo + 1); } if (mx >= 7) { ret.push_back(vector<int>(N + 1, 0)); for (int t = 0; t < 4; t++) ret.push_back(vector<int>(N + 1, 0)); for (int t = 0; t < 4; t++) ret[x + 1 + t][0] = 1; vector<int>&v = ret[x]; v[0] = 0; for (int i = 0; i < (int)S.size(); i++) { int lo = S[i].first; int hi = S[i].second; v[lo] = -1; v[hi] = -2; lo++; hi--; int sz = hi - lo + 1; if (sz >= 1) { int k = (sz + 3) / 4; k = max(k, 2); for (int t = 0; t < 4; t++) { int l = lo + t * k; int r = lo + (t + 1) * k - 1; r = min(r, hi); if (l <= r) { for (int i = l; i <= r; i++) { ret[(x + 1) + t][i] = x + 5; v[i] = x + 1 + t; } for (int i = lo - 1; i <= l; i++) { ret[(x + 1) + t][i] = -2; } for (int i = r; i <= hi + 1; i++) { ret[(x + 1) + t][i] = -1; } if (r - l + 1 > 2) { S_.push_back({l, r}); } } } } } S = S_; } else if (mx >= 5) { ret.push_back(vector<int>(N + 1, 0)); for (int t = 0; t < 3; t++) ret.push_back(vector<int>(N + 1, 0)); for (int t = 0; t < 3; t++) ret[x + 1 + t][0] = 1; vector<int>&v = ret[x]; v[0] = 0; for (int i = 0; i < (int)S.size(); i++) { int lo = S[i].first; int hi = S[i].second; v[lo] = -1; v[hi] = -2; lo++; hi--; int sz = hi - lo + 1; if (sz >= 1) { int k = (sz + 2) / 3; k = max(k, 2); for (int t = 0; t < 3; t++) { int l = lo + t * k; int r = lo + (t + 1) * k - 1; r = min(r, hi); if (l <= r) { for (int i = l; i <= r; i++) { ret[(x + 1) + t][i] = x + 4; v[i] = x + 1 + t; } for (int i = lo - 1; i <= l; i++) { ret[(x + 1) + t][i] = -2; } for (int i = r; i <= hi + 1; i++) { ret[(x + 1) + t][i] = -1; } if (r - l + 1 > 2) { S_.push_back({l, r}); } } } } } S = S_; } else if (mx >= 3) { ret.push_back(vector<int>(N + 1, 0)); for (int t = 0; t < 2; t++) ret.push_back(vector<int>(N + 1, 0)); for (int t = 0; t < 2; t++) ret[x + 1 + t][0] = 1; vector<int>&v = ret[x]; v[0] = 0; for (int i = 0; i < (int)S.size(); i++) { int lo = S[i].first; int hi = S[i].second; v[lo] = -1; v[hi] = -2; lo++; hi--; int sz = hi - lo + 1; if (sz >= 1) { int k = (sz + 1) / 2; k = max(k, 2); for (int t = 0; t < 2; t++) { int l = lo + t * k; int r = lo + (t + 1) * k - 1; r = min(r, hi); if (l <= r) { for (int i = l; i <= r; i++) { ret[(x + 1) + t][i] = x + 3; v[i] = x + 1 + t; } for (int i = lo - 1; i <= l; i++) { ret[(x + 1) + t][i] = -2; } for (int i = r; i <= hi + 1; i++) { ret[(x + 1) + t][i] = -1; } if (r - l + 1 > 2) { S_.push_back({l, r}); } } } } } S = S_; } else if (mx >= 1) { ret.push_back(vector<int>(N + 1, 0)); for (int t = 0; t < 1; t++) ret.push_back(vector<int>(N + 1, 0)); for (int t = 0; t < 1; t++) ret[x + 1 + t][0] = 1; vector<int>&v = ret[x]; v[0] = 0; for (int i = 0; i < (int)S.size(); i++) { int lo = S[i].first; int hi = S[i].second; v[lo] = -1; v[hi] = -2; lo++; hi--; int sz = hi - lo + 1; if (sz >= 1) { int k = (sz + 1) / 1; k = max(k, 2); for (int t = 0; t < 1; t++) { int l = lo + t * k; int r = lo + (t + 1) * k - 1; r = min(r, hi); if (l <= r) { for (int i = l; i <= r; i++) { ret[(x + 1) + t][i] = x + 2; v[i] = x + 1 + t; } for (int i = lo - 1; i <= l; i++) { ret[(x + 1) + t][i] = -2; } for (int i = r; i <= hi + 1; i++) { ret[(x + 1) + t][i] = -1; } if (r - l + 1 > 2) { S_.push_back({l, r}); } } } } } S = S_; } else { ret.push_back(vector<int>(N + 1, 0)); vector<int>&v = ret[x]; v[0] = 0; for (int i = 0; i < (int)S.size(); i++) { int lo = S[i].first; int hi = S[i].second; v[lo] = -1; v[hi] = -2; } S = S_; } } int mx = (int)ret.size() - 1; for (vector<int> &i : ret) for (int &j : i) j = min(j, mx); return ret; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...