oj.uz

답안 #859111

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
859111 2023-10-09T17:53:10 Z vgtcross Flight to the Ford (BOI22_communication) C++17
0 / 100
 2485 ms 3208 KB 
#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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 332 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 85.0

# 결과 실행 시간 메모리 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 -