제출 #643697

#제출 시각아이디문제언어결과실행 시간메모리
643697blue죄수들의 도전 (IOI22_prison)C++17
36.50 / 100
18 ms1672 KiB
#include "prison.h" #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; using pii = pair<int, int>; using vpii = vector<pii>; using vvpii = vector<vpii>; #define sz(x) int(x.size()) const int lg = 13; vi pow3 = vi(1 + lg); int getdigit(int i, int d) { if(d < 0) return 0; return (i / pow3[d]) % 3; } vvi devise_strategy(int N) { pow3[0] = 1; for(int e = 1; e <= lg; e++) pow3[e] = 3 * pow3[e-1]; vvi s(3*lg+1, vi(1+N, -1)); s[0][0] = 0; for(int i = 1; i <= N; i++) { s[0][i] = 1 + getdigit(i, lg-1); } for(int p = 0; p < lg; p++) { int b = lg-1 - p; if(p % 2 == 0) //even bit, check B { s[3*p + 1][0] = 1; s[3*p + 2][0] = 1; s[3*p + 3][0] = 1; for(int i = 1; i <= N; i++) { int cd = getdigit(i, b); //current digit for(int wd = 0; wd <= 2; wd++) //whiteboard digit { if(cd < wd) { s[3*p + 1 + wd][i] = -2; } else if(wd < cd) { s[3*p + 1 + wd][i] = -1; } else s[3*p + 1 + wd][i] = 3*(p+1) + 1 + getdigit(i, b-1); } } } else //odd bit, check A { s[3*p + 1][0] = 0; s[3*p + 2][0] = 0; s[3*p + 3][0] = 0; for(int i = 1; i <= N; i++) { int cd = getdigit(i, b); //current digit for(int wd = 0; wd <= 2; wd++) //whiteboard digit { if(cd < wd) { s[3*p + 1 + wd][i] = -1; } else if(wd < cd) { s[3*p + 1 + wd][i] = -2; } else s[3*p + 1 + wd][i] = 3*(p+1) + 1 + getdigit(i, b-1); } } } } int x = sz(s) - 1; for(int i = 0; i < sz(s); i++) for(int j = 0; j <= N; j++) if(s[i][j] > x) s[i][j] = -1; // for(int i = 0; i <= x; i++) // { // for(int j = 0; j <= N; j++) // { // cerr << i << ' ' << j << " : " << s[i][j] << '\n'; // } // } return s; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...