제출 #825441

#제출 시각아이디문제언어결과실행 시간메모리
825441esomer죄수들의 도전 (IOI22_prison)C++17
0 / 100
4 ms724 KiB
#include <bits/stdc++.h> #include "prison.h" using namespace std; typedef long long ll; int N; vector<vector<int>> ans, inds; vector<int> dp, which, sizes; vector<vector<pair<int, int>>> ranges; 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; } } } } } int get_groups(int i, vector<vector<pair<int, int>>>& ranges){ pair<int, int> pr = ranges[i][0]; int curr = 0; int groups = 0; for(int j = pr.first + 1; j < pr.second; j++) { curr++; if(curr == sizes[i + 1] || j == pr.second - 1) { groups++; curr = 0; } } return groups; } vector<vector<int>> devise_strategy(int n) { N = n; calc_dp(); int total = N; while(total > 2){ sizes.push_back(total); int x = which[total]; total -= 2; int nw = total / x; if(total % x != 0) nw++; total = nw; } sizes.push_back(total); ranges.assign((int)sizes.size(), {}); inds.assign((int)sizes.size(), {}); ranges[0].push_back({1, N}); inds[0].push_back(0); ans.assign(21, vector<int>(N+1, 0)); vector<int> col(N + 1, 0); int curr_ind = 1; for(int i = 0; i < (int)sizes.size(); i++){ if(i == (int)sizes.size() - 1){ for(int ind : inds[i]){ for(pair<int, int> pr : ranges[i]){ if(col[pr.first] == ind){ ans[ind][pr.first] = -(ans[ind][0] + 1); ans[ind][pr.second] = -((1 - ans[ind][0]) + 1); if(pr.first > 1) ans[ind][pr.first - 1] = -(ans[ind][0] + 1); if(pr.second < N) ans[ind][pr.second + 1] = -((1 - ans[ind][0]) + 1); }else{ for(int j = pr.first; j <= pr.second; j++) { if(col[j] > ind) { ans[ind][j] = -(ans[ind][0] + 1); }else{ ans[ind][j] = -((1 - ans[ind][0]) + 1); } } } } } // cout << "i " << i << " sizes "<< sizes[i] << endl; // cout << "INDS: "; // for(int x : inds[i]) cout << x << " "; cout << endl; // cout << "Ranges: "; // for(pair<int, int> pr : ranges[i]) cout << pr.first << " " << pr.second << endl; // cout << "Col: "; // for(int x : col) cout << x << " "; cout << endl; continue; } int groups = get_groups(i, ranges); for(int j = 0; j < groups; j++){ ans[curr_ind][0] = 1 - ans[inds[i][0]][0]; inds[i+1].push_back(curr_ind); curr_ind++; } vector<int> nwcol(N+1, 0); for(int ind : inds[i]){ for(pair<int, int> pr : ranges[i]){ if(col[pr.first] == ind){ ans[ind][pr.first] = -(ans[ind][0] + 1); ans[ind][pr.second] = -((1 - ans[ind][0]) + 1); if(pr.first > 1) ans[ind][pr.first - 1] = -(ans[ind][0] + 1); if(pr.second < N) ans[ind][pr.second + 1] = -((1 - ans[ind][0]) + 1); int curr = 0; int cind = 0; int lst = pr.first + 1; for(int j = pr.first + 1; j < pr.second; j++) { curr++; ans[ind][j] = inds[i + 1][cind]; nwcol[j] = inds[i + 1][cind]; if(curr == sizes[i + 1] || j == pr.second - 1) { ranges[i+1].push_back({lst, j}); curr = 0; cind++; lst = j + 1; } } }else{ for(int j = pr.first; j <= pr.second; j++) { if(col[j] > ind) { ans[ind][j] = -(ans[ind][0] + 1); }else{ ans[ind][j] = -((1 - ans[ind][0]) + 1); } } } } } col = nwcol; // cout << "i " << i << " sizes "<< sizes[i] << endl; // cout << "INDS: "; // for(int x : inds[i]) cout << x << " "; cout << endl; // cout << "Ranges: "; // for(pair<int, int> pr : ranges[i]) cout << pr.first << " " << pr.second << endl; // cout << "Col: "; // for(int x : col) cout << x << " "; cout << endl; } return ans; } // static constexpr int kNumPrisoners = 500; // static void invalid_strategy(std::string message) { // printf("%s\n", message.c_str()); // exit(0); // } // int main() { // int N2; // assert(1 == scanf("%d", &N2)); // // printf("here\n"); return 0; // std::vector<std::vector<int>> strategy = devise_strategy(N2); // // printf("here\n"); return 0; // if (strategy.size() == 0) { // invalid_strategy("s is an empty array"); // } // int x = strategy.size() - 1; // for (int i = 0; i <= x; ++i) { // if (static_cast<int>(strategy[i].size()) != N2 + 1) { // invalid_strategy("s[i] contains incorrect length"); // } // if (strategy[i][0] < 0 || strategy[i][0] > 1) { // invalid_strategy("First element of s[i] is non-binary"); // } // for (int j = 1; j <= N2; ++j) { // if (strategy[i][j] < -2 || strategy[i][j] > x) { // invalid_strategy("s[i][j] contains incorrect value"); // } // } // } // // printf("here\n"); return 0; // FILE *log_file = fopen("log.txt","w"); // int A, B; // while (1 == scanf("%d", &A) && A != -1) { // assert(1 == scanf("%d", &B)); // bool answer = false; // int whiteboard = 0; // for (int i = 0; i < kNumPrisoners && !answer; ++i) { // int check = strategy[whiteboard][0]; // whiteboard = strategy[whiteboard][check == 0 ? A : B]; // if (whiteboard < 0) { // answer = true; // printf("%c\n", "BA"[whiteboard + 2]); // } else { // if (i > 0) { // fprintf(log_file, " "); // } // fprintf(log_file, "%d", whiteboard); // } // } // if (!answer) { // printf("X\n"); // } // fprintf(log_file, "\n"); // fflush(log_file); // } // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...