Submission #859142

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
859142	2023-10-09T19:50:16 Z	vgtcross	Flight to the Ford (BOI22_communication)	C++17	0 / 100	2684 ms	3436 KB

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);
        for (pii p : ins) s.insert(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();
        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;
        }
    }
}

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);
        for (pii p : ins) s.insert(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();
        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.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	28 ms	352 KB	Not correct
2	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	498 ms	2756 KB	Output is partially correct
2	Partially correct	236 ms	2732 KB	Output is partially correct
3	Partially correct	308 ms	2740 KB	Output is partially correct
4	Partially correct	599 ms	2940 KB	Output is partially correct
5	Partially correct	498 ms	3032 KB	Output is partially correct
6	Partially correct	456 ms	2756 KB	Output is partially correct
7	Partially correct	1631 ms	2784 KB	Output is partially correct
8	Partially correct	2684 ms	3436 KB	Output is partially correct
9	Partially correct	2130 ms	2848 KB	Output is partially correct
10	Partially correct	2403 ms	2952 KB	Output is partially correct
11	Partially correct	2289 ms	3100 KB	Output is partially correct
12	Partially correct	2342 ms	3052 KB	Output is partially correct
13	Partially correct	2275 ms	2932 KB	Output is partially correct
14	Partially correct	2401 ms	2864 KB	Output is partially correct
15	Partially correct	1192 ms	3108 KB	Output is partially correct
16	Partially correct	2612 ms	2816 KB	Output is partially correct
17	Partially correct	663 ms	3060 KB	Output is partially correct
18	Partially correct	608 ms	3152 KB	Output is partially correct
19	Partially correct	692 ms	3088 KB	Output is partially correct
20	Partially correct	704 ms	2788 KB	Output is partially correct
21	Partially correct	651 ms	3060 KB	Output is partially correct
22	Partially correct	619 ms	2804 KB	Output is partially correct
23	Partially correct	1089 ms	2808 KB	Output is partially correct
24	Incorrect	25 ms	352 KB	Not correct
25	Halted	0 ms	0 KB	-