Submission #1009671

#TimeUsernameProblemLanguageResultExecution timeMemory
1009671somefjordPrisoner Challenge (IOI22_prison)C++17
10 / 100
8 ms1116 KiB
#include "prison.h" #include <algorithm> #include <bits/stdc++.h> using namespace std; constexpr int DEBUG = 0; int log2(int v) { int r = 0; while (v >>= 1) { r++; } return r + 1; } int pack(int pos, int b) { return (((pos) << 1) | ((b & 1) << 0)) + 1; } vector<vector<int>> devise_strategy(int N) { int nbits = 13; // log2(N); int x = ((nbits - 1) << 1) | 0b1; if (DEBUG) printf("nbits: %d, x: %d\n", nbits, x); vector<vector<int>> s(x, vector<int>(N + 1)); int maxi = 0; // pos -> previous pos for (int pos = 0; pos < nbits - 1; ++pos) { int bitpos = nbits - 1 - pos; // b -> previously inspected bit for (int b = 0; b <= 1; ++b) { // IF we last checked A, lastab = 0 auto lastab = (pos % 2); int i = pack(pos, b); maxi = max(i, maxi); // IF we last checked A -> check B next, and vice-versa s[i][0] = !lastab; if (DEBUG > 1) printf("[%d] prev pos: %d, prev bitpos: %d, prev b: %d -> check: %d\n", i, pos, bitpos, b, s[i][0]); // v -> the current value for (int v = 1; v <= N; ++v) { bool prevselfset = (v >> bitpos) & 1; if (prevselfset && !b) { s[i][v] = lastab ? -2 : -1; } else if (!prevselfset && b) { s[i][v] = lastab ? -1 : -2; } else if (bitpos > 1) { bool selfset = (v >> (bitpos - 1)) & 1; s[i][v] = pack(pos + 1, selfset); } else { bool selfset = v & 1; if (selfset) { s[i][v] = lastab ? -2 : -1; } else { s[i][v] = lastab ? -1 : -2; } } if (DEBUG > 22) printf(" s[%d][%d] = %d\n", i, v, s[i][v]); } } } // whiteboard is always 0 initially bool startab = 0; s[0][0] = startab; for (int v = 1; v <= N; ++v) { bool selfset = (v >> (nbits - 1)) & 1; if (nbits == 13 && selfset) { s[0][v] = pack(2, 0); } else { s[0][v] = pack(0, selfset); } } // If the value is 1, then it's the least s[0][1] = -1; // vice-versa s[0][N] = -2; if (DEBUG > 2) { vector<bool> visited(x, false); for (int i = 0; i < x; ++i) { for (int v = 1; v <= N; ++v) { printf("%d %d\n", i, s[i][v]); if (s[i][v] >= 0) visited[s[i][v]] = true; } } for (int i = 1; i < x; ++i) { if (!visited[i]) printf("[!] Unvisited: %d\n", i); } } if (DEBUG) printf("maxi: %d\n", maxi); return s; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...