Submission #737228

#	Time	Username	Problem	Language	Result	Execution time	Memory
737228		rainliofficial	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	15 ms	1128 KiB

prison

#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 = 12;
    vector<vector<int>> s(25, vector<int>(N+1));
    // vector<int> po3;
    // po3[0] = 1;
    // for (int i=1; i<=8; i++){
    //     po3[i] = po3[i-1] * 3;
    // }
    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<=24; ){
        int which = (x-1) % 4 < 2 ? 2 : 1;
        int other = (x-1) % 4 < 2 ? 1 : 2;
        if (x <= 21 && x % 2 == 1) s[x+2][0] = s[x+3][0] = (s[x][0] + 1)%2;
        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] = -other; // this current bag is larger
                else{ // they have equal bits up to now
                    if ((i & (1<<(lg2-1)))){
                        if (lg2 - 1 == 0) s[x][i] = -other;
                        else s[x][i] = x+3;
                    }else{
                        if (lg2 - 1 == 0) s[x][i] = -which;
                        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)))){
                        if (lg2 - 1 == 0) s[x][i] = -other;
                        else s[x][i] = x+2;
                    }else{
                        if (lg2 - 1 == 0) s[x][i] = -which;
                        else s[x][i] = x+1;
                    }
                }else s[x][i] = -which; // the other bag is larger
            }
        }
        if (x % 2 == 0){
            lg2--;
        }
        x++;
    }
    assert(lg2 == 0);
    return s;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 55 / 90