제출 #652102

#제출 시각아이디문제언어결과실행 시간메모리
652102blue죄수들의 도전 (IOI22_prison)C++17
100 / 100
13 ms1236 KiB
#include "prison.h" #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; #define sz(x) int(x.size()) const int stp = 21; int N; vector<string> addr; //'L' = left end, 'R' = right end, //'0' = part 0, '1' = part 1, '2' = part 2 vi dp(1+stp); vi inv(1 + 6'000); vi spl(1+stp); vi dep; void selfmax(int& a, int b) { a = max(a, b); } void build_tree(int l, int r, int i) { // cerr << "build tree " << l << ' ' << r << ' ' << i << " : " << dp[i] << '\n'; assert(l != r); addr[l].push_back('L'); l++; addr[r].push_back('R'); r--; if(i == 1) { return; } else if(i == 2) { addr[l].push_back('0'); addr[l+1].push_back('0'); build_tree(l, l+1, 1); } else { int k; if(dp[i] == 3*dp[i-3] + 2) k = 3; else k = 2; int j = (r-l+1)/k; for(int ki = 0; ki < k; ki++) { int l1 = l + j*ki; int r1 = l + j*(ki+1) - 1; for(int n = l1; n <= r1; n++) addr[n].push_back('0' + ki); build_tree(l1, r1, i-k); } } } vvi devise_strategy(int N_) { dp[0] = -100; dp[1] = 2; dp[2] = 4; for(int i = 3; i <= stp; i++) { if(i-3 >= 1) selfmax(dp[i], 3*dp[i-3] + 2); if(i-2 >= 1) selfmax(dp[i], 2*dp[i-2] + 2); if(dp[i] == 3*dp[i-3] + 2) spl[i] = 3; else spl[i] = 2; } spl[2] = 1; spl[1] = 0; for(int i = 1; i <= stp; i++) inv[dp[i]] = i; // for(int i = stp; i >= 1; i--) // cerr << dp[i] << " : " << spl[i] << '\n'; // cerr << "\n\n\n\n"; N = dp[stp]; // cerr << "N value = " << N << '\n'; addr = vector<string>(1+N, ""); build_tree(1, N, stp); // cerr << "terminate\n"; // for(int i = 1; i <= N; i++) // cerr << i << " : " << addr[i] << '\n'; int x = dp[stp]; vvi res(stp, vi(1+N, 0)); vi depsiz; vi depspl; vvi depind; // cerr << "\n\n\n"; for(int z = N; z >= 3; z = (z-2)/spl[inv[z]]) { depsiz.push_back(z); depspl.push_back(spl[inv[z]]); // cerr << z << " : " << spl[inv[z]] << '\n'; } // cerr << 2 << " : " << 1 << '\n'; depsiz.push_back(2); depspl.push_back(1); // cerr << "\n\n\n"; int u = 1; for(int d = 0; d < sz(depsiz)-1; d++) { depind.push_back({}); for(int e = 0; e < depspl[d]; e++) { depind[d].push_back(u++); } } // cerr << "u = " << u << '\n'; // depind.push_back({{u++}}); //person 0, checks A res[0][0] = 0; for(int i = 1; i <= N; i++) { if(addr[i][0] == 'L') res[0][i] = -1; else if(addr[i][0] == 'R') res[0][i] = -2; else { res[0][i] = depind[0][ addr[i][0] - '0' ]; } } // cerr << "done\n"; // cerr << "sz = " << sz(depsiz) << '\n'; for(int d = 0; d < sz(depsiz)-1; d++) //even depth, check B odd depth, check A { for(int z = 0; z < depspl[d]; z++) { int xi = depind[d][z]; // cerr << d << ", " << z << " -> " << xi << '\n'; // cerr << "xi = " << xi << '\n'; //d even -> check A, odd -> check B if(d % 2 == 0) res[xi][0] = 1; else res[xi][1] = 0; for(int i = 1; i <= N; i++) { // cerr << "i = " << i << '\n'; // if(xi == 1 && i == 9) // { // cerr << "z = " << z << '\n'; // cerr << "hello, " << addr[i][d] << '\n'; // } // cerr << "i = " << i << '\n'; if(sz(addr[i]) - 1 < d) { res[xi][i] = 0; } if(addr[i][d] == 'L') { // cerr << "case 1\n"; if(d % 2 == 0) res[xi][i] = -2; else res[xi][i] = -1; } else if(addr[i][d] == 'R') { // cerr << "case 2\n"; if(d % 2 == 0) res[xi][i] = -1; else res[xi][i] = -2; } else if(addr[i][d] - '0' < z) { if(d % 2 == 0) res[xi][i] = -2; else res[xi][i] = -1; } else if(addr[i][d] - '0' > z) { if(d % 2 == 0) res[xi][i] = -1; else res[xi][i] = -2; } else if(addr[i][d] - '0' == z) { // cerr << "case 3\n"; // cerr << i << " : " << d+1 << ' ' << sz(addr[i]) << '\n'; if(addr[i][d+1] == 'L') { if(d % 2 == 0) res[xi][i] = -2; else res[xi][i] = -1; } else if(addr[i][d+1] == 'R') { if(d % 2 == 0) res[xi][i] = -1; else res[xi][i] = -2; } else res[xi][i] = depind[d+1][addr[i][d+1] - '0']; } } // cerr << "z done\n"; } // cerr << "d = " << d << " done\n"; } // int ld = sz(depsiz) - 1; // int lx = stp-1; // cerr << "\n\n\n\n\n\n"; // cerr << "ld = " << ld << '\n'; // if(ld % 2 == 0) // { // res[ld][0] = 1; // for(int i = 1; i <= N; i++) // { // if(sz(addr[i]) - 1 < ld) // { // res[lx][i] = 0; // } // else if(addr[i][ld] == 'L') // res[lx][i] = -2; // else // res[lx][i] = -1; // } // } // else // { // res[ld][0] = 0; // for(int i = 1; i <= N; i++) // { // if(sz(addr[i]) - 1 < ld) // { // res[lx][i] = 0; // } // else if(addr[i][ld] == 'L') // res[lx][i] = -1; // else // res[lx][i] = -2; // } // } for(int xi = 0; xi < stp; xi++) res[xi].resize(1+N_); // cerr << "res size = " << sz(res) << '\n'; // for(vi f : res) // cerr << sz(f) << '\n'; // cerr << "original N = " << N_ << '\n'; // for(int xi = 0; xi < stp; xi++) // { // for(int u : res[xi]) // cerr << u << ' '; // cerr << '\n'; // } // cerr << addr[7] << "\n" << addr[8] << '\n'; // cerr << "columns\n"; // for(int xv = 0; xv < stp; xv++) // cerr << res[xv][7] << ' ' << res[xv][8] << '\n'; // cerr << "\n\n"; return res; }

컴파일 시 표준 에러 (stderr) 메시지

prison.cpp: In function 'vvi devise_strategy(int)':
prison.cpp:118:6: warning: unused variable 'x' [-Wunused-variable]
  118 |  int x = dp[stp];
      |      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...