Submission #1012000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012000		Unforgettablepl	Shopping (JOI21_shopping)	C++17	100 / 100	151 ms	12756 KiB

Anna

#include "Anna.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;

const int BLOCK_SIZE = 1382;


namespace {
int L, R;
vector<bool> buffer;
int ptr = 0;
bool read(){
    assert(ptr<buffer.size());
    return buffer[ptr++];
}

int get(int l,int r){
    vector<int> depth(2*BLOCK_SIZE+1);
    vector<int> p(2*BLOCK_SIZE+1);
    vector<int> actual(2*BLOCK_SIZE+1);
    int c = 0;
    int act = 0;
    int ll = -1,rr = -1;
    function<void(int,int)> readtree = [&](int par,int dep){
        p[c] = par;
        depth[c] = dep;
        int myc = c;
        c++;
        bool hasleft = read();
        bool hasright = read();
        if(hasleft)readtree(myc,dep+1);
        if(act==l)ll=myc;
        if(act==r)rr=myc;
        actual[myc] = act;
        act++;
        if(hasright)readtree(myc,dep+1);
    };
    readtree(-1,1);
    if(depth[ll]<depth[rr])swap(ll,rr);
    while(depth[ll]>depth[rr])ll = p[ll];
    while(true){
        if(ll==rr)return actual[ll];
        ll = p[ll];
        rr = p[rr];
    }
    assert(false);
}
}  // namespace

void InitA(int N, int L, int R) {
    ::L = L;
    ::R = R;
    int curr = 0;
    for(int i=0;i<724;i++){
        for(int j=i;j<724;j++){
            curr++;
            if(i==L/BLOCK_SIZE and j==R/BLOCK_SIZE)break;
        }
        if(i==L/BLOCK_SIZE)break;    
    }
    for(int bit=0;bit<18;bit++)SendA(curr&(1<<bit));
}

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

int Answer() {
    int middle_man = 0;
    for(int i=0;i<20;i++)if(read())middle_man|=(1<<i);
    int ll = L%BLOCK_SIZE;
    int rr = R%BLOCK_SIZE;
    if(L/BLOCK_SIZE!=R/BLOCK_SIZE)rr+=BLOCK_SIZE+1;
    int ans = get(ll,rr);
    if(ans==BLOCK_SIZE)return middle_man;
    if(ans<BLOCK_SIZE)return ans+(L/BLOCK_SIZE)*BLOCK_SIZE;
    if(ans>BLOCK_SIZE)return ans-BLOCK_SIZE-1+(R/BLOCK_SIZE)*BLOCK_SIZE;
    assert(false);
}

Bruno

#include "Bruno.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int BLOCK_SIZE = 1382;

namespace {
vector<int32_t> P;
int N;
int cnt;
int num;
void generate(vector<pair<int,int>> arr){
    int n = arr.size();
    vector<pair<int,int>> tree(n+1,{-1,-1});
    vector<pair<int,int>> best(n);
    stack<pair<int,int>> s;
    s.emplace(0,-1);
    for(int i=0;i<n;i++){
        while(arr[i].second<s.top().first)s.pop();
        best[i] = s.top();
        s.emplace(arr[i].second,i);
    }
    while(!s.empty())s.pop();
    s.emplace(0,n);
    for(int i=n-1;i>=0;i--){
        while(arr[i].second<=s.top().first)s.pop();
        best[i] = max(best[i],s.top());
        if(best[i].second<i)tree[best[i].second].second=i;
        else tree[best[i].second].first=i;
        s.emplace(arr[i].second,i);
    }
    function<void(int)> dfs = [&](int x){
        if(x==-1)return;
        SendB(tree[x].first!=-1);
        SendB(tree[x].second!=-1);
        dfs(tree[x].first);
        dfs(tree[x].second);
    };
    dfs(tree[n].first);
}
}  // namespace

void InitB(int32_t N, std::vector<int32_t> P) {
    ::N = N;
    ::P = P;
}

void ReceiveB(bool y) {
    if(y)num|=1<<cnt;
    cnt++;
    if(cnt==18){
        int curr = 0;
        int l = -1,r = -1;
        for(int i=0;i<724;i++){
            for(int j=i;j<724;j++){
                if(++curr==num){
                    l = i;
                    r = j;
                }
            }
        }
        vector<pair<int,int>> arr;
        int t;
        for(int i=l*BLOCK_SIZE;i<(l+1)*BLOCK_SIZE;i++){
            if(i<N)arr.emplace_back(i,P[i]);
            else arr.emplace_back(i,1e10+(t++));
        }
        pair<int,int> currmin = {1e10+(t++),200000};
        for(int i=(l+1)*BLOCK_SIZE;i<r*BLOCK_SIZE;i++){
            currmin = min(currmin,{P[i],i});
        }
        for(int i=0;i<20;i++){
            if(currmin.second&(1<<i))SendB(true);
            else SendB(false);
        }
        arr.emplace_back(currmin.second,currmin.first);
        for(int i=r*BLOCK_SIZE;i<(r+1)*BLOCK_SIZE;i++){
            if(i<N)arr.emplace_back(i,P[i]);
            else arr.emplace_back(i,1e10+(t++));
        }
        generate(arr);
    }
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from Anna.cpp:3:
Anna.cpp: In function 'bool {anonymous}::read()':
Anna.cpp:14:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     assert(ptr<buffer.size());
      |            ~~~^~~~~~~~~~~~~~

Bruno.cpp: In function 'void ReceiveB(bool)':
Bruno.cpp:67:41: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |             else arr.emplace_back(i,1e10+(t++));
      |                                     ~~~~^~~~~~

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