Submission #859117

#	Time	Username	Problem	Language	Result	Execution time	Memory
859117		vgtcross	Flight to the Ford (BOI22_communication)	C++17	0 / 100	271 ms	512 KiB

communication

#include <bits/stdc++.h>

#define MODE 0

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int send(int s)
#if MODE
{
    cout << "send " << s << endl;
    cin >> s;
    return s;
}
#else
;
#endif

int receive()
#if MODE
{
    cout << "receive: " << flush;
    int s;
    cin >> s;
    return s;
}
#else
;
#endif

int write(int s) {
    //cout << "w: " << s << '\n';
    if (s == 1) {
        int p = 0;
        while (p == 0) p = send(1);
        return send(1) + 2;
    } else {
        int p = 2;
        while (p--) if (send(0)) return send(3 - s) + 2;
        return 1;
    }
}

const int N = 1e9;

void encode(int n, int x) {
    set<pii> s;
    s.insert({1, N + 1});
    int len = N;
    while (len > 2) {
        int mid1 = len / 3;
        int mid2 = 2 * len / 3;
        int cum = 0;
        for (pii p : s) {
            if (x >= p.second) cum += p.second - p.first;
            else {
                cum += x - p.first;
                break;
            }
        }
        
        int b;
        if (cum < mid1) b = write(1);
        else if (cum < mid2) b = write(2);
        else b = write(3);
        //cout << "r: " << b << '\n';
        
        set<pii> l, r, era, ins;
        
        int cur = 0;
        for (pii p : s) {
            if (cur == mid1) break;
            if (cur + p.second - p.first <= mid1) {
                l.insert(p);
                era.insert(p);
                cur += p.second - p.first;
            } else {
                l.insert({p.first, p.first + mid1 - cur});
                ins.insert({p.first + mid1 - cur, p.second});
                era.insert(p);
                cur = mid1;
            }
        }
        for (pii p : era) s.erase(p);
        era.clear();
        ins.clear();
        
        for (pii p : s) {
            if (cur == mid2) break;
            if (cur + p.second - p.first <= mid2) {
                r.insert(p);
                era.insert(p);
                cur += p.second - p.first;
            } else {
                r.insert({p.first, p.first + mid2 - cur});
                ins.insert({p.first + mid2 - cur, p.second});
                era.insert(p);
                cur = mid2;
            }
        }
        for (pii p : era) s.erase(p);
        for (pii p : ins) s.insert(p);
        era.clear();
        
        if (b == 1) {
            for (pii p : r) s.insert(p);
            len -= mid1;
        } else if (b == 2) {
            for (pii p : l) s.insert(p);
            len -= mid2 - mid1;
        } else {
            for (pii p : r) l.insert(p);
            swap(l, s);
            len -= len - mid2;
        }
    }
}

int read() {
    if (receive()) return receive() + 2;
    if (receive()) return receive() + 2;
    return 1;
}

pair<int, int> decode(int n) {
    set<pii> s;
    s.insert({1, N + 1});
    int len = N;
    while (len > 2) {
        int mid1 = len / 3;
        int mid2 = 2 * len / 3;
        int b = read();
        
        set<pii> l, r, era, ins;
        
        int cur = 0;
        for (pii p : s) {
            if (cur == mid1) break;
            if (cur + p.second - p.first <= mid1) {
                l.insert(p);
                era.insert(p);
                cur += p.second - p.first;
            } else {
                l.insert({p.first, p.first + mid1 - cur});
                ins.insert({p.first + mid1 - cur, p.second});
                era.insert(p);
                cur = mid1;
            }
        }
        for (pii p : era) s.erase(p);
        era.clear();
        
        for (pii p : s) {
            if (cur == mid2) break;
            if (cur + p.second - p.first <= mid2) {
                r.insert(p);
                era.insert(p);
                cur += p.second - p.first;
            } else {
                r.insert({p.first, p.first + mid2 - cur});
                ins.insert({p.first + mid2 - cur, p.second});
                era.insert(p);
                cur = mid2;
            }
        }
        for (pii p : era) s.erase(p);
        for (pii p : ins) s.insert(p);
        era.clear();
        ins.clear();
        
        if (b == 1) {
            for (pii p : r) s.insert(p);
            len -= mid1;
        } else if (b == 2) {
            for (pii p : l) s.insert(p);
            len -= mid2 - mid1;
        } else {
            for (pii p : r) l.insert(p);
            swap(l, s);
            len -= len - mid2;
        }
    }
    
    if (s.size() == 1) return {s.begin()->first, s.begin()->first+1};
    else {
        pii p;
        auto it = s.begin();
        p.first = it->first;
        ++it;
        p.second = it->first;
        return p;
    }
}

#if MODE
int main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    int n, x;
    cin >> n >> x;
    encode(n, x);
    cout << "\n\nmode swich\n\n\n";
    pair<int, int> p = decode(n);
    cout << "! " << p.first << ' ' << p.second << endl;
}
#endif

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