oj.uz

Submission #579855

# Submission time Handle Problem Language Result Execution time Memory
579855 2022-06-20T06:08:56 Z balbit Flight to the Ford (BOI22_communication) C++17
74 / 100
 3733 ms 1948 KB 
#include <bits/stdc++.h>
#ifndef BALBIT
#include "communication.h"
#endif // BALBIT
using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second

#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

#define MX(a,b) a=max(a,b)
#define MN(a,b) a = min(a,b)
#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do( T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT

int lst[] = {0b0000, 0b0110, 0b1001, 0b1111};
int which[1<<4];
vector<int> chg;

void build(){
    chg.clear();
    REP(ty, (1<<4)) {
        bool ok = 1;
        REP(j,3) {
            if ((ty & (1<<j)) && (ty & (1<<(j+1)))) {
                ok = 0;
            }
        }
        if (ok) chg.pb(ty);
    }
    memset(which, -1, sizeof which);
    REP(i,4) {
        which[lst[i]] = i;
    }
}

#ifdef BALBIT

queue<int> rar;
bool canflip = 1;
int send(int x){
    if (canflip && rand()%2) {
        rar.push(x^1); canflip = 0;
    }else{
        rar.push(x);
        canflip = 1;
    }
    bug(rar.back());
    return rar.back();
}

int receive() {
    int re = rar.front(); rar.pop();
    return re; //rar.pop();
}
#endif // BALBIT

set<vector<int> > st;
pii who(int x) {
    vector<int> re;
    for (int m : chg) {
        if (which[m^x] != -1) {
            re.pb(which[m^x]);
        }
    }
    assert(SZ(re) <= 2);
    sort(ALL(re));
//    st.insert(re);
    return {re[0], re[1]};
//    bug(re[0], re[1]);
}

pii trysend(int x) {
    assert(x >= 0 && x <= 3);
    int reallysend = 0;
    REP(j,4) {
        bool bit = (lst[x] >> j) & 1;
        int went = send(bit);
        reallysend += (went<<j);
    }
    return who(reallysend);
}

pii eat4(){
    int raw=0;
    REP(j,4) {
        raw += (receive()) << j;
    }
    bug(raw);
    return who(raw);
}

pii gfrom(pii org, pii t) {
    pii re;
    re.f = (t.f>=2?org.s:org.f) * 2 + (t.f&1);
    re.s = (t.s>=2?org.s:org.f) * 2 + (t.s&1);
    if (re.f > re.s) swap(re.f, re.s);
    return re;
}

void encode(signed N, signed X) {
    build();
    --X;

    int cur = ((X>>29)&1)*2 + ((X>>28)&1);

    pii pp = trysend(cur);


    for (int bit = 27; bit >=0; --bit) {
        int tosend = 0;
        if (pp.s == cur) tosend = 2;
        tosend += (X>>bit)&1;
        pii go = trysend(tosend);
        pp = gfrom(pp, go);
        cur = cur * 2 + ((X>>bit)&1);
    }

}

pair<signed, signed> decode(signed N) {
    build();

    pii ee = eat4();

    for (int bit = 27; bit >=0; --bit) {
        pii gt = eat4();
        ee = gfrom(ee, gt);
    }

    bug(ee.f, ee.s);
    MN(ee.f, N-1); MN(ee.s, N-1);
    return {ee.f+1, ee.s+1};
}

#ifdef BALBIT

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    srand(time(0));
//    build();
//    REP(i,(1<<4)) {
//        bug(i);
//        who(i);
////        for (int t : who(i)) cout<<t<<' ';
////        cout<<endl;
//    }
//    for (vector<int> e : st) {
//        bug(e[0], e[1]);
//    }

//    bug(1,2);

    while (SZ(rar)) rar.pop(); canflip = 1;

    encode(1000000000, 1000000000);
    pii p = decode(1000000000);
    bug(p.f, p.s);
}
#endif

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 1716 KB Output is correct
2 Correct 151 ms 1704 KB Output is correct
3 Correct 231 ms 1684 KB Output is correct
4 Correct 88 ms 1684 KB Output is correct
5 Correct 127 ms 1684 KB Output is correct
6 Correct 317 ms 1788 KB Output is correct
7 Correct 574 ms 1680 KB Output is correct

Subtask #2
59.00003 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 917 ms 1716 KB Output is partially correct
2 Partially correct 344 ms 1700 KB Output is partially correct
3 Partially correct 483 ms 1680 KB Output is partially correct
4 Partially correct 619 ms 1720 KB Output is partially correct
5 Partially correct 836 ms 1680 KB Output is partially correct
6 Partially correct 773 ms 1748 KB Output is partially correct
7 Partially correct 2241 ms 1856 KB Output is partially correct
8 Partially correct 3733 ms 1948 KB Output is partially correct
9 Partially correct 3336 ms 1824 KB Output is partially correct
10 Partially correct 3279 ms 1828 KB Output is partially correct
11 Partially correct 3159 ms 1840 KB Output is partially correct
12 Partially correct 3088 ms 1840 KB Output is partially correct
13 Partially correct 2964 ms 1792 KB Output is partially correct
14 Partially correct 3037 ms 1884 KB Output is partially correct
15 Partially correct 1474 ms 1844 KB Output is partially correct
16 Partially correct 3526 ms 1828 KB Output is partially correct
17 Partially correct 897 ms 1732 KB Output is partially correct
18 Partially correct 938 ms 1884 KB Output is partially correct
19 Partially correct 826 ms 1844 KB Output is partially correct
20 Partially correct 925 ms 1808 KB Output is partially correct
21 Partially correct 822 ms 1848 KB Output is partially correct
22 Partially correct 1040 ms 1800 KB Output is partially correct
23 Partially correct 1486 ms 1764 KB Output is partially correct
24 Correct 95 ms 1808 KB Output is correct
25 Correct 145 ms 1668 KB Output is correct
26 Correct 241 ms 1676 KB Output is correct
27 Correct 81 ms 1664 KB Output is correct
28 Correct 144 ms 1720 KB Output is correct
29 Correct 361 ms 1764 KB Output is correct
30 Correct 772 ms 1840 KB Output is correct