Submission #736576

#TimeUsernameProblemLanguageResultExecution timeMemory
736576rainliofficialPrisoner Challenge (IOI22_prison)C++17
0 / 100
1 ms212 KiB
#include "prison.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } #define sz(x) (int)x.size() #define all(x) begin(x), end(x) void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '\"' << x << '\"';} void __print(const string &x) {cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x); template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifdef DEBUG #define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl; #else #define dbg(x...) #endif /* Date: 2023/05/03 10:14 Problem Link: Topic(s): Reflection: Solution Notes: The most straightforward solution is to keep write the number of coins seen in the bad onto the board. This takes O(N) numbers to do. Then we notice the first subtask is something to do with sqrt. What if we keep track a sqrt size block for every number we write on the board? Consider blocking into sqrt, and for every block, we run the original linear algorithm, but only on that block. ceil(sqrt(500)) = 23 There are 23 blocks, and we can have at most 23 numbers in each block. The full solution should involve some kind of log factor. Consider considering the bit of every number. log2(5000) = 13 We can do this in 26 states. Prisoner 1 checks A for the 2^12th bit, if bit=0: write 1 if bit=1: write 2 Prisoner 2: sees 1: checks if B has 2^12th bit on if yes: output B > A else: if 2^11th bit not on: write 3 else: write 4 sees 2: checks if B has 2^12 bit on if yes: if 2^11th bit not on: write 3 else: write 4 else: output A > B 0 mod 2 -> bit on 1 mod 2 -> bit off */ const int MAXN = 2e5+5, INF = 1e9; vector<vector<int>> devise_strategy(int N){ int lg2 = 13; vector<vector<int>> s(lg2 * 2 + 1, vector<int>(N+1)); for (int i=1; i<=N; i++){ if ((i & (1<<lg2))) s[0][i] = 2; else s[0][i] = 1; } s[1][0] = 1; s[2][0] = 1; for (int x=1; x<=26; ){ int which = (x-1) % 4 < 2 ? 2 : 1; int other = (which + 1)%2; if (x <= 23 && x % 2 == 1) s[x+2][0] = other, s[x+3][0] = other; for (int i=1; i<=N; i++){ if (x % 2 == 1){ // bit is off in the other bag if ((i & (1<<lg2))) s[x][i] = -which; // this current bag is larger else{ // they have equal bits up to now if ((i & (1<<(lg2-1)))) s[x][i] = x+3; else s[x][i] = x+2; } }else{ // bit is on in the other bag if ((i & (1<<lg2))){ // bits equal up to now if ((i & (1<<(lg2-1)))) s[x][i] = x+2; else s[x][i] = x+1; } else s[x][i] = -other; // the other bag is larger } } if (x % 2 == 0){ lg2--; } x++; } return s; } // int main(){ // cin.tie(0); ios_base::sync_with_stdio(0); // // freopen("file.in", "r", stdin); // // freopen("file.out", "w", stdout); // vector<vector<int>> x = devise_strategy(3); // dbg(x); // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...