Submission #859111

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
859111	2023-10-09T17:53:10 Z	vgtcross	Flight to the Ford (BOI22_communication)	C++17	0 / 100	2485 ms	3208 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) {
    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);
        
        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	26 ms	332 KB	Not correct
2	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	516 ms	2988 KB	Output is partially correct
2	Partially correct	244 ms	2764 KB	Output is partially correct
3	Partially correct	306 ms	2956 KB	Output is partially correct
4	Partially correct	570 ms	3008 KB	Output is partially correct
5	Partially correct	441 ms	2936 KB	Output is partially correct
6	Partially correct	359 ms	2772 KB	Output is partially correct
7	Partially correct	1563 ms	2836 KB	Output is partially correct
8	Partially correct	2481 ms	3208 KB	Output is partially correct
9	Partially correct	2308 ms	2932 KB	Output is partially correct
10	Partially correct	2366 ms	2952 KB	Output is partially correct
11	Partially correct	2371 ms	2932 KB	Output is partially correct
12	Partially correct	2082 ms	3188 KB	Output is partially correct
13	Partially correct	2146 ms	2956 KB	Output is partially correct
14	Partially correct	2406 ms	2932 KB	Output is partially correct
15	Partially correct	1174 ms	2792 KB	Output is partially correct
16	Partially correct	2485 ms	3056 KB	Output is partially correct
17	Partially correct	688 ms	2916 KB	Output is partially correct
18	Partially correct	594 ms	2812 KB	Output is partially correct
19	Partially correct	698 ms	3052 KB	Output is partially correct
20	Partially correct	678 ms	2816 KB	Output is partially correct
21	Partially correct	667 ms	2884 KB	Output is partially correct
22	Partially correct	638 ms	2884 KB	Output is partially correct
23	Partially correct	1074 ms	2868 KB	Output is partially correct
24	Incorrect	23 ms	332 KB	Not correct
25	Halted	0 ms	0 KB	-