Submission #580197

#	Time	Username	Problem	Language	Result	Execution time	Memory
580197		wiwiho	Flight to the Ford (BOI22_communication)	C++17	100 / 100	3519 ms	2152 KiB

communication

#include"communication.h"

#include <bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define ef emplace_front
#define pob pop_back()
#define pof pop_front()
#define mp make_pair
#define F first
#define S second
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

const int SZ = 4;

struct Node{
    vector<pii> a, b;
    int sizea(){
        int sum = 0;
        for(pii i : a) sum += i.S - i.F + 1;
        return sum;
    }
    int sizeb(){
        int sum = 0;
        for(pii i : b) sum += i.S - i.F + 1;
        return sum;
    }
    int size(){
        return sizea() + sizeb();
    }
    bool ina(int v){
        for(pii i : a){
            if(i.F <= v && v <= i.S) return true;
        }
        return false;
    }
    bool inb(int v){
        for(pii i : b){
            if(i.F <= v && v <= i.S) return true;
        }
        return false;
    }
    vector<int> num(){
        vector<int> ans;
        for(pii i : a){
            for(int j = i.F; j <= i.S; j++) ans.eb(j);
        }
        for(pii i : b){
            for(int j = i.F; j <= i.S; j++) ans.eb(j);
        }
        return ans;
    }
};

pair<Node, Node> split(Node v){
    Node ln, rn;

    int len = v.sizea();
    int now = 0;
    int ls = (len + 1) / 2;
    for(pii i : v.a){
        if(now + i.S - i.F + 1 <= ls){
            ln.a.eb(i);
            rn.b.eb(i);
            now += i.S - i.F + 1;
            continue;
        }
        if(now >= ls){
            rn.a.eb(i);
            ln.b.eb(i);
            continue;
        }
        int tmp = ls - now;
        now = ls;
        ln.a.eb(mp(i.F, i.F + tmp - 1));
        rn.b.eb(mp(i.F, i.F + tmp - 1));
        rn.a.eb(mp(i.F + tmp, i.S));
        ln.b.eb(mp(i.F + tmp, i.S));
    }

    len = v.sizeb();
    now = 0;
    ls = len / 2;
    for(pii i : v.b){
        if(now + i.S - i.F + 1 <= ls){
            ln.a.eb(i);
            now += i.S - i.F + 1;
            continue;
        }
        if(now >= ls){
            rn.a.eb(i);
            continue;
        }
        int tmp = ls - now;
        now = ls;
        ln.a.eb(mp(i.F, i.F + tmp - 1));
        rn.a.eb(mp(i.F + tmp, i.S));
    }

    /*cerr << "split " << v.sizea() << " " << v.sizeb() << "\n";
    cerr << " left " << ln.sizea() << " " << ln.sizeb() << "\n";
    cerr << " right " << rn.sizea() << " " << rn.sizeb() << "\n";*/

    return mp(ln, rn);
}

void sendnum(int v){
    for(int i = 0; i < 4; i++){
        if(1 << i & v) send(1);
        else send(0);
    }
}

int readnum(){
    int v = 0;
    for(int i = 0; i < 4; i++){
        if(receive()) v |= 1 << i;
    }
    return v;
}

void encode(int N, int X) {

    Node now;
    now.a.eb(mp(1, 1000000000));

    while(now.size() > 3){
        Node l, r;
        tie(l, r) = split(now);

        int nxt;
        if(l.ina(X)) nxt = 0;
        else nxt = 1;

        nxt = send(nxt);
        if(nxt == 0) now = l;
        else now = r;
    }

    vector<int> num = now.num();
    vector<int> owo = {0b0000, 0b0110, 0b1001};
    for(int i = 0; i < num.size(); i++){
        if(X == num[i]){
            sendnum(owo[i]);
            return;
        }
    }

}

pii decode(int N) {

    Node now;
    now.a.eb(mp(1, 1000000000));

    while(now.size() > 3){
        Node l, r;
        tie(l, r) = split(now);

        int nxt = receive();
        if(nxt == 0) now = l;
        else now = r;
    }

    vector<int> num = now.num();
    while(num.size() < 3) num.eb(1);
    int X = readnum();

    vector<int> tans;
    for(int i = 0; i < (1 << 4); i++){
        bool ok = true;
        for(int j = 0; j + 1 < SZ; j++){
            if((1 << j & i) && (1 << (j + 1) & i)) ok = false;
        }
        if(!ok) continue;
        int tmp = X ^ i;
        if(tmp == 0b0000) tans.eb(num[0]);
        else if(tmp == 0b0110) tans.eb(num[1]);
        else if(tmp == 0b1001) tans.eb(num[2]);
    }

    vector<int> ans;
    for(int i : tans){
        if(i <= N) ans.eb(i);
    }
    while(ans.size() < 2) ans.eb(ans[0]);

    return mp(ans[0], ans[1]);
}

Compilation message (stderr)

communication.cpp: In function 'void encode(int, int)':
communication.cpp:160:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |     for(int i = 0; i < num.size(); i++){
      |                    ~~^~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85