Submission #709535

#	Time	Username	Problem	Language	Result	Execution time	Memory
709535		kostia244	Shopping (JOI21_shopping)	C++17	100 / 100	194 ms	20460 KiB

Anna

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

namespace {
//common
#define send_f SendA
const int anna_bits = 18, len_bits = 4;
int get_bit(int msk, int i) {
    return (msk >> i) & 1;
}
int equal_bits, step;
struct BitIO {
    int read_val = 0;
    queue<int> val_buffer, reads;
    bool process_read(bool bit) {
        if(reads.size()) {
            read_val = 2 * read_val + bit;
            reads.front()--;
            if(reads.front() == 0) {
                val_buffer.push(read_val);
                reads.pop();
                read_val = 0;
            }
        }
        return reads.size();
    }
    void order_read(int x) {
        if(x) {
            reads.push(x);
        }
    }
    int extract_read() {
        int ret = val_buffer.front();
        val_buffer.pop();
        return ret;
    }

    void send_bits(int msk, int x) {
        for(int i = x; i--;)
            send_f(get_bit(msk, i));
    }
};
BitIO io;
//end common

int n, l, r;
int l1, l2, r1, r2;
vector<int> p;
}  // namespace

void InitA(int n_, int l_, int r_) {
    n = n_, l = l_, r = r_;
    p.resize(1<<20, 1<<20);

    for(int i = 19; i >= 0 &&
        get_bit(l, i) == get_bit(r, i); i--)
        equal_bits++;
    equal_bits = min(equal_bits, anna_bits - len_bits);

    int pos = r_ >> (20 - equal_bits);
    io.send_bits(equal_bits, len_bits);
    io.send_bits(pos, equal_bits);
    io.order_read(20);
    io.order_read(20);

    step = 4 + equal_bits;

    int B = (1 << (19 - equal_bits));
    pos = (pos << (20 - equal_bits)) + B;
    l1 = r1 = pos;//get_segment(1)
    l2 = pos - B;//get_segment(2*B)
    r2 = pos + B;
}

void ReceiveA(bool x) {
    if(io.process_read(x))
        return;

    if(step < anna_bits) {
        int ll = io.extract_read(), rr = io.extract_read();
        cerr << "Alice " << step << " " << l << " " << r << endl;
        cerr << "ll, rr: " << ll << " " << rr << endl;
        int contains = !(ll < l && r <= rr);
        SendA(contains);
        if(contains) {
            l1 = ll, r1 = rr;
        } else {
            l2 = ll, r2 = rr;
        }
        step++;
    }

    if(step < anna_bits) {
        io.order_read(20);
        io.order_read(20);
    } else if(step == anna_bits) {
        io.order_read(20);
        io.order_read(20);
        io.order_read(20);
        io.order_read(20);
        step++;
    } else if(step == anna_bits + 1) {
        l1 = io.extract_read();
        r1 = io.extract_read();
        l2 = io.extract_read();
        r2 = io.extract_read();
        
        for(int i = l2; i <= l1; i++)
            io.order_read(20);
        io.order_read(20);
        io.order_read(20);
        io.order_read(20);
        io.order_read(20);
        for(int i = r1; i <= r2; i++)
            io.order_read(20);
        step++;
    }
}

int Answer() {
    for(int i = l2; i <= l1; i++) {   
        p[i] = io.extract_read();
    }
    
    int mn_pos = io.extract_read();
    p[mn_pos] = io.extract_read();
    mn_pos = io.extract_read();
    p[mn_pos] = io.extract_read();

    for(int i = r1; i <= r2; i++) {
        p[i] = io.extract_read();
    }
    int pos = min_element(p.begin() + l, p.begin() + r + 1) - p.begin();
    cerr << "final: " << pos << " : " << l1 << " " << r1 << " " << l2 << " " << r2 << endl;
    return pos;
}

Bruno

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

namespace {
//common
#define send_f SendB
const int anna_bits = 18, len_bits = 4;
int get_bit(int msk, int i) {
    return (msk >> i) & 1;
}
int equal_bits, step;
struct BitIO {
    int read_val = 0;
    queue<int> val_buffer, reads;
    bool process_read(bool bit) {
        if(reads.size()) {
            read_val = 2 * read_val + bit;
            reads.front()--;
            if(reads.front() == 0) {
                val_buffer.push(read_val);
                reads.pop();
                read_val = 0;
            }
        }
        return reads.size();
    }
    void order_read(int x) {
        if(x) {
            reads.push(x);
        }
    }
    int extract_read() {
        int ret = val_buffer.front();
        val_buffer.pop();
        return ret;
    }

    void send_bits(int msk, int x) {
        for(int i = x; i--;)
            send_f(get_bit(msk, i));
    }
};
BitIO io;
//end common

int n, pos, L, R, low, high;
vector<int> p;

}  // namespace

void InitB(int N, std::vector<int> P) {
    n = N;
    n = max(n, 1<<20);
    p = P;
    while(p.size() < n)
        p.push_back(1 + p.size());
    step = -1;
    io.order_read(len_bits);
}

array<int, 2> get_segment(int len) {
    int l = pos, r = pos;
    int lmin, rmin;
    lmin = rmin = p[pos];
    while(--len > 0) {
        if(r + 1 == R || (lmin >= rmin && l > L)) {
            lmin = min(lmin, p[--l]);
        } else {
            rmin = min(rmin, p[++r]);
        }
    }
    cerr << "F: " << lmin << " " << rmin << endl;
    return {l, r};
}

void ReceiveB(bool y) {
    if(io.process_read(y))
        return;
    if(step == -1) {
        equal_bits = io.extract_read();
        low = 1;
        high = 1<<(20 - equal_bits);
        if(equal_bits) {
            io.order_read(equal_bits);
            step = -2;
            return;
        } else {
            pos = 1<<19;
            L = 0;
            R = 1<<20;
            step = 0;
        }
    }
    if(step == -2) {
        pos = (io.extract_read()<<(20 - equal_bits));
        int B = 1<<(19 - equal_bits);
        pos += B;
        L = pos - B;
        R = pos + B;
        step = equal_bits;
    }
    cerr << "Bruno: " << step << " " << pos << " " << equal_bits << endl;
    cerr << "L, R: " << " " << L << " " << R << endl;
    cerr << "low, high: " << " " << low << " " << high << endl;

    if(step == anna_bits - len_bits) {//final iteration
        auto [l1, r1] = get_segment(low);
        auto [l2, r2] = get_segment(high);
        io.send_bits(l1, 20);
        io.send_bits(r1, 20);
        io.send_bits(l2, 20);
        io.send_bits(r2, 20);
        cerr << "final: " << pos << " : " << l1 << " " << r1 << " " << l2 << " " << r2 << endl;
        for(int i = l2; i <= l1; i++) {
            io.send_bits(p[i], 20);
        }
        
        int mn_pos = min_element(p.begin() + l1, p.begin() + pos + 1) - p.begin();
        io.send_bits(mn_pos, 20);
        io.send_bits(p[mn_pos], 20);
        
        mn_pos = min_element(p.begin() + pos, p.begin() + r1 + 1) - p.begin();
        io.send_bits(mn_pos, 20);
        io.send_bits(p[mn_pos], 20);

        for(int i = r1; i <= r2; i++) {
            io.send_bits(p[i], 20);
        }
        return;
    }

    int mid = (low + high) / 2;
    if(step > equal_bits) {
        if(y)
            low = mid;
        else
            high = mid;
        mid = (low + high) / 2;
        cerr << "update low, high: " << low << " " << high << endl;
    }

    auto [l, r] = get_segment(mid);
    cerr << "send (l, r) = (" << l << ", " << r << ") | mid = " << mid << endl;
    io.send_bits(l, 20);
    io.send_bits(r, 20);
    step++;
}

Compilation message (stderr)

Bruno.cpp: In function 'void InitB(int, std::vector<int>)':
Bruno.cpp:56:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |     while(p.size() < n)
      |           ~~~~~~~~~^~~

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