Submission #622340

#	Time	Username	Problem	Language	Result	Execution time	Memory
622340		maomao90	Shopping (JOI21_shopping)	C++17	100 / 100	218 ms	16168 KiB

Anna

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
#include "Anna.h"
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 1000005;
const int BLK = 1384;

namespace {
    int n, l, r;
    vector<bool> bits;
    int ans;
}

void InitA(int N, int L, int R) {
    n = N; l = L; r = R;
    int lb = l / BLK, rb = r / BLK;
    int bn = (n - 1) / BLK + 1;
    int id = 0;
    REP (i, 0, lb) {
        id += bn - i;
    }
    id += rb - lb;
    cerr << lb << ' ' << rb << ' ' << id << '\n';
    assert(id < (1 << 18));
    RREP (k, 17, 0) {
        SendA(id >> k & 1);
    }
    ans = -1;
}

void ReceiveA(bool x) {
    bits.pb(x);
    if (SZ(bits) == (2 * BLK + 1) * 2 + 20) {
        int lb = l / BLK, rb = r / BLK;
        int bn = (n - 1) / BLK + 1;
        if (lb == rb) {
            int id = lb * BLK;
            vi stk;
            for (bool x : bits) {
                if (x) {
                    if (id >= l) {
                        stk.pb(id);
                    }
                    if (id == r) {
                        ans = stk[0];
                        return;
                    }
                    id++;
                } else {
                    if (!stk.empty()) {
                        stk.pop_back();
                    }
                }
            }
        } else {
            int mid = 0;
            REP (k, 0, 20) {
                mid += bits.back() << k;
                bits.pop_back();
            }
            int id = lb * BLK;
            cerr << mid << ' ' << id << '\n';
            vi stk;
            for (bool x : bits) {
                cerr << ' ' << id << ' ' << x << '\n';
                if (x) {
                    if (id >= l) {
                        stk.pb(id);
                        cerr << "+ " << id << '\n';
                    }
                    if (id == r) {
                        ans = stk[0];
                        return;
                    }
                    id++;
                    if (id == (lb + 1) * BLK) {
                        id = mid;
                    } else if (id == mid + 1) {
                        id = rb * BLK;
                    }
                } else {
                    if (!stk.empty()) {
                        cerr << "- " << stk.back() << '\n';
                        stk.pop_back();
                    }
                }
            }
        }
    }
    assert(SZ(bits) <= (2 * BLK + 1) * 2 + 20);
}

int Answer() {
    assert(ans != -1);
    cerr << "! " << ans << '\n';
    return ans;
}

Bruno

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
#include "Bruno.h"
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 1000005;
const int BLK = 1384;

namespace {
    int n;
    vi p;
    int cnt;
    int id;
}

void InitB(int N, vi P) {
    n = N; p = P;
    cnt = 0;
    id = 0;
    while (n % BLK != 0) {
        n++;
        p.pb(INF);
    }
}

void ReceiveB(bool y) {
    id *= 2;
    id += y;
    if (++cnt == 18) {
        int bn = (n - 1) / BLK + 1;
        int lb = -1, rb = -1;
        REP (i, 0, bn) {
            if (bn - i <= id) {
                id -= bn - i;
            } else {
                lb = i;
                rb = i + id;
                break;
            }
        }
        cerr << lb << ' ' << rb << '\n';
        assert(lb != -1);
        vi stk;
        REP (i, lb * BLK, (lb + 1) * BLK) {
            while (!stk.empty() && stk.back() >= p[i]) {
                SendB(0);
                cerr << '0';
                stk.pop_back();
            }
            SendB(1);
            cerr << '1';
            stk.pb(p[i]);
        }
        ii mid = {INF, (1 << 20) - 1};
        if (lb < rb) {
            REP (i, (lb + 1) * BLK, rb * BLK) {
                mnto(mid, {p[i], i});
            }
        }
        while (!stk.empty() && stk.back() >= mid.FI) {
            SendB(0);
            cerr << '0';
            stk.pop_back();
        }
        SendB(1);
        cerr << '1';
        stk.pb(mid.FI);
        REP (i, rb * BLK, (rb + 1) * BLK) {
            while (!stk.empty() && stk.back() >= p[i]) {
                SendB(0);
                cerr << '0';
                stk.pop_back();
            }
            SendB(1);
            cerr << '1';
            stk.pb(p[i]);
        }
        while (!stk.empty()) {
            SendB(0);
            cerr << '0';
            stk.pop_back();
        }
        cerr << '\n';
        assert(mid.SE < (1 << 20));
        cerr << mid.FI << ' ' << mid.SE << '\n';
        RREP (k, 19, 0) {
            SendB(mid.SE >> k & 1);
        }
    }
    assert(cnt <= 18);
}

Compilation message (stderr)

Anna.cpp: In function 'void ReceiveA(bool)':
Anna.cpp:67:13: warning: unused variable 'bn' [-Wunused-variable]
   67 |         int bn = (n - 1) / BLK + 1;
      |             ^~

• Subtask 1: 1 / 1
• Subtask 2: 9 / 9
• Subtask 3: 90 / 90