제출 #947211

#제출 시각아이디문제언어결과실행 시간메모리
947211Nhoksocqt1죄수들의 도전 (IOI22_prison)C++17
56 / 100
25 ms99164 KiB
#ifndef Nhoksocqt1 #include "prison.h" #endif // Nhoksocqt1 #include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f #define sz(x) int((x).size()) #define fi first #define se second typedef long long ll; typedef pair<int, int> ii; template<class X, class Y> inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);} template<class X, class Y> inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int Random(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); } const int MAXN = 5003; int ans[MAXN][MAXN], nArr; vector<vector<int>> devise_strategy(int _N) { nArr = _N; for (int i = 0; i <= max(26, nArr); ++i) { ans[i][0] = 0; for (int j = 1; j <= nArr; ++j) ans[i][j] = -1; } int x(0); ans[0][0] = 0; for (int j = 1; j <= nArr; ++j) ans[0][j] = x + 1 + (j >> 12 & 1); x += 2; for (int i = 12; i >= 0; --i) { ans[x - 1][0] = ans[x][0] = !(i & 1); for (int j = 1; j <= nArr; ++j) { if(j >> i & 1) { ans[x - 1][j] = (i & 1) ? -2 : -1; if(i > 0) ans[x][j] = x + 1 + (j >> (i - 1) & 1); } else { ans[x][j] = (i & 1) ? -1 : -2; if(i > 0) ans[x - 1][j] = x + 1 + (j >> (i - 1) & 1); } } if(i > 0) x += 2; } vector<vector<int>> res; for (int i = 0; i <= x; ++i) { vector<int> p; for (int j = 0; j <= nArr; ++j) p.push_back(ans[i][j]); res.push_back(p); } return res; } #ifdef Nhoksocqt1 int main(void) { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); #define TASK "prison" if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); } int _N; cin >> _N; vector<vector<int>> ans = devise_strategy(_N); cout << "X USED: " << sz(ans) - 1 << '\n'; for (int i = 0; i < sz(ans); ++i) { for (int j = 0; j < sz(ans[i]); ++j) cout << ans[i][j] << ' '; cout << '\n'; } for (int A = 1; A <= _N; ++A) { for (int B = 1; B <= _N; ++B) { if(A == B) continue; int x(0); while(1) { int y = ans[x][0] ? B : A; x = ans[x][y]; //cout << x << ' ' << y << '\n'; if(x == -1) { if(A < B) { cout << "OK WITH PAIR " << A << ' ' << B << " !!\n"; break; } else { cout << "WRONG WITH PAIR " << A << ' ' << B << " !!\n"; exit(1); } } else if(x == -2) { if(A > B) { cout << "OK WITH PAIR " << A << ' ' << B << " !!\n"; break; } else { cout << "WRONG WITH PAIR " << A << ' ' << B << " !!\n"; exit(1); } } } } } return 0; } #endif // Nhoksocqt1
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...