Submission #1230049

#TimeUsernameProblemLanguageResultExecution timeMemory
1230049badge881Prisoner Challenge (IOI22_prison)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h> #include "prison.h" using namespace std; const int iTakeA = -1, iTakeB = -2; vector<vector<int>> devise_strategy(int N) { vector<vector<int>> result(37, vector<int>(N + 1, 0)); int power = 12; for (int i = 0; i < 12; i++) { for (int j = 1; j <= N; j++) if (j == 1) result[12][j] = iTakeA; // prend sac A else if (j == N) result[12][j] = iTakeB; // prend sac B else if (j & (1 << power)) result[i][j] = 13 + i; else result[i][j] = 25 + i; power--; } // cas final on verifie la pow 0 (0 ou 1) et on decide directement car forcement differents for (int j = 1; j <= N; j++) { if (j == 1) result[12][j] = iTakeA; // prend sac A else if (j == N) result[12][j] = iTakeB; // prend sac B else if (j % 2 == 0) result[12][j] = iTakeA; // prend sac A else result[12][j] = iTakeB; // prend sac B } power = 12; for (int i = 13; i < 25; i++) { // sac A a la power `power` active result[i][0] = 1; for (int j = 1; j <= N; j++) if (j == 1) result[12][j] = iTakeB; // prend sac A else if (j == N) result[12][j] = iTakeA; // prend sac B else if (j & (1 << power)) result[i][j] = i - 12; else result[i][j] = iTakeB; // prend sac B power--; } power = 12; for (int i = 25; i < 37; i++) { // sac A a la power `power` disactive result[i][0] = 1; for (int j = 1; j <= N; j++) if (j == 1) result[12][j] = iTakeB; // prend sac A else if (j == N) result[12][j] = iTakeA; // prend sac B else if (j & (1 << power)) result[i][j] = iTakeA; // prend sac A else result[i][j] = i - 24; power--; } return result; } #ifdef HOME int main() { int N = 5000; vector<vector<int>> result = devise_strategy(N); // for (int i = 0; i < 37; i++) // { // cout << "I read " << i << " on board, I will see bag " << result[i][0] << " and write on board: "; // for (int j = 1; j <= N; j++) // cout << result[i][j] << " "; // cout << endl; // } random_device rd; uniform_int_distribution<> dis(1, N); int distribution = 0; for (int sacA = 1; sacA <= N; sacA++) for (int sacB = 1; sacB <= N; sacB++) { int tab = 0; if (sacA == sacB) continue; while (tab >= 0) if (result[tab][0] == 0) tab = result[tab][sacA]; else tab = result[tab][sacB]; if ((tab == iTakeA && sacA < sacB) or (tab == iTakeB && sacA > sacB)) distribution += sacA < sacB ? 1 : -1; else cout << "I lose! A = " << sacA << " B = " << sacB << endl; } return 0; } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...