Submission #1238153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238153		Double_Slash	Shopping (JOI21_shopping)	C++20	10 / 100	90 ms	16684 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>

using namespace std;
#define all(x) x.begin(), x.end()
using pint = pair<int, int>;

namespace {
    const int K = 1500;
    int N, L, R, l, r;
    vector<int> bits;
}

void InitA(int N, int L, int R) {
    ::N = N, ::L = L, ::R = R;
    vector<pint> v;
    if (N <= K) v.emplace_back(N, N);
    else {
        for (int l = K; l < N; l += K) {
            for (int r = l; r < N; r += K) v.emplace_back(l, r);
        }
    }
    cerr << v.size() << endl;
    sort(all(v));
    l = L / K + 1, r = R / K + 1;
    r -= r != l;
    int i = lower_bound(all(v), pint{l *= K, r *= K}) - v.begin();
    if (i == v.size()) --i;
    tie(l, r) = v[i];
    cerr << l << ' ' << r << ' ' << i << endl;
    for (int j = 18; j--;) SendA((i >> j) & 1);
}

void ReceiveA(bool x) { bits.emplace_back(x); }

int Answer() {
    vector<int> a;
    for (int i = max(l - K, 0); i < min(N, l); ++i) a.emplace_back(i);
    if (l < r) {
        a.emplace_back(0);
        for (int j = 18; j--;) a.back() |= bits[j] << j;
        bits.erase(bits.begin(), bits.begin() + 18);
        cerr << a.back() << endl;
    }
    for (int i = r; i < min(r + K, N); ++i) a.emplace_back(i);
    cerr << "A read\n";
    bits.resize(bits.size() + K * 2 + 1);
    reverse(all(bits));
    vector<int> st;
    cerr << a.end()[-4] << endl;
    for (int i = 0; i < a.size(); ++i) {
        for (; bits.back(); bits.pop_back()) {
            if (st.back() == 9676) cerr << a[i] << endl;
            st.pop_back();
        }
        // for (; bits.back(); bits.pop_back()) cerr << a[i] << ' ' << st.back() << endl, st.pop_back();
        st.emplace_back(a[i]);
        bits.pop_back();
        if (i + 1 == a.size() or a[i + 1] > R) {
            cerr << *lower_bound(all(st), L) << endl;
            return *lower_bound(all(st), L);
        }
    }
    assert(false);
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>

using namespace std;
#define all(x) x.begin(), x.end()
using pint = pair<int, int>;

namespace {
    const int K = 1500;
    int N, idx = 0, bit = 18;
    vector<pint> v;
	vector<int> P;
}

void InitB(int N, vector<int> P) {
	::N = N, ::P = P;
    if (N <= K) v.emplace_back(N, N);
    else {
        for (int l = K; l < N; l += K) {
            for (int r = l; r < N; r += K) v.emplace_back(l, r);
        }
    }
	sort(all(v));
    cerr << v.size() << endl;
}

void ReceiveB(bool y) {
	idx |= y << --bit;
	if (bit) return;
    auto [l, r] = v[idx];
    cerr << l << ' ' << r << ' ' << idx << endl;
    vector<int> a;
    for (int i = max(l - K, 0); i < l; ++i) a.emplace_back(i);
    vector<bool> bits;
    if (l < r) {
        a.emplace_back(l);
        for (int i = l; ++i < r;) {
            if (P[i] < P[a.back()]) a.back() = i;
        }
        for (int j = 0; j < 18; ++j) bits.emplace_back((a.back() >> j) & 1);
    }
    for (int i = r; i < min(N, r + K); ++i) a.emplace_back(i);
    vector<int> st;
    for (int i = 0; i < a.size(); ++i) {
        for (; not st.empty() and P[st.back()] > P[a[i]]; st.pop_back()) {
            if (st.back() == 9676) cerr << a[i] << endl;
            bits.emplace_back(true);
        }
        st.emplace_back(a[i]);
        bits.emplace_back(false);
    }
    while (not bits.empty() and not bits.back()) bits.pop_back();
    for (bool b: bits) SendB(b);
    cerr << "B done\n";
}

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