oj.uz

답안 #859142

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
859142 2023-10-09T19:50:16 Z vgtcross Flight to the Ford (BOI22_communication) C++17
0 / 100
 2684 ms 3436 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) {
    //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

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

Subtask #2
0.0 / 85.0

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