제출 #825311

#제출 시각아이디문제언어결과실행 시간메모리
825311esomer죄수들의 도전 (IOI22_prison)C++17
5 / 100
11 ms19216 KiB
#include <bits/stdc++.h> #include "prison.h" using namespace std; typedef long long ll; int N; vector<vector<int>> ans; vector<int> dp, which; void build(int ind, int l, int r) { int total = r - l + 1; if(total <= 2){ // cout << "ind " << ind << " total " << total << " l " << l << " r " << r << endl; for(int i = 1; i <= N; i++){ if(i < l){ ans[ind][i] = -(ans[ind][0] + 1); }else if(i > r){ ans[ind][i] = -((1 - ans[ind][0]) + 1); }else if(i == l){ ans[ind][l] = -(ans[ind][0] + 1); }else if(i == r) { ans[ind][r] = -((1 - ans[ind][0]) + 1); } // cout << "ind "<< ind << " i " << i << " " << ans[ind][i] << endl; } return; } int x = which[total]; total -= 2; vector<int> sizes(x, total / x); for(int i = 0; i < total % x; i++){ sizes[i]++; } // cout << "ind " << ind << " x " << x << " total " << total << endl; int curr = 0; int cind = 0; for(int i = 1; i <= N; i++){ if(i < l){ ans[ind][i] = -(ans[ind][0] + 1); }else if(i > r){ ans[ind][i] = -((1 - ans[ind][0]) + 1); }else if(i == l){ ans[ind][l] = -(ans[ind][0] + 1); }else if(i == r) { ans[ind][r] = -((1 - ans[ind][0]) + 1); }else{ curr++; ans[ind][i] = (int)ans.size(); if(curr >= sizes[cind]){ ans.push_back({}); ans[(int)ans.size() - 1].resize(N+1); ans[(int)ans.size() - 1][0] = 1 - ans[ind][0]; build((int)ans.size() - 1, i - curr + 1, i); curr = 0; cind++; } } // cout << "ind "<< ind << " i " << i << " " << ans[ind][i] << endl; } } void calc_dp(){ dp.assign(N+1, 1e9); which.assign(N+1, 1); for(int i = 0; i <= N; i++){ int real = i - 2; if(real <= 0) dp[i] = 0; else{ for(int x = 1; x <= 20; x++){ int cll = real / x; if(real % x != 0) cll++; int needed = x + dp[cll]; if(needed < dp[i]){ which[i] = x; dp[i] = needed; } } } } } vector<vector<int>> devise_strategy(int n) { N = n; calc_dp(); ans.push_back({}); ans[0].resize(N+1); ans[0][0] = 0; build(0, 1, N); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...