oj.uz

Submission #579870

# Submission time Handle Problem Language Result Execution time Memory
579870 2022-06-20T07:05:51 Z balbit Flight to the Ford (BOI22_communication) C++17
74 / 100
 3326 ms 2060 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 RREP(i,n) for (int i = n-1; i>=0 ;--i)
#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};

const int len = 4;

int which[1<<len];
vector<int> chg;

//int occupied[1<<len];
vector<int> pref[5][1<<len];

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

    for (int L = 4; L>=1; --L) {
        if (L == 4) {
            REP(x, (1<<4)) {
                vector<int> re;
                for (int m : chg) {
                    if (which[m^x] != -1) {
                        re.pb(which[m^x]);
                    }
                }
                sort(ALL(re));
                assert(SZ(re) <= 2);
                pref[L][x] = re;
            }
        }else{
            REP(x, (1<<L)) {
                vector<int> tmp = pref[L+1][x*2];
                tmp.insert(tmp.end(), ALL(pref[L+1][x*2+1]));
                sort(ALL(tmp)); tmp.resize(unique(ALL(tmp)) - tmp.begin());
                if (SZ(tmp) <= 2) {
                    bug("yay!!!!", L, x);
                }
//                tmp.pb(-1);
                pref[L][x] = tmp;

            }
        }
    }
}

#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 = pref[4][x];
//    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;
    RREP(j,4) {
        bool bit = (lst[x] >> j) & 1;
        int went = send(bit);
        reallysend = reallysend * 2 + went;
        if (SZ(pref[4-j][reallysend]) <= 2) {
            assert(x == pref[4-j][reallysend][0] || x == pref[4-j][reallysend][1]);
            return {pref[4-j][reallysend][0], pref[4-j][reallysend][1]};
        }
    }
    assert(0);
//    return who(reallysend);
}

pii eat4(){
    int raw=0;
    REP(j,4) {
        int yar = receive();
        raw = raw * 2 + yar;
        if (SZ(pref[j+1][raw]) <= 2) {
            return {pref[j+1][raw][0], pref[j+1][raw][1]};
        }
    }
    assert(0);
    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);
    int cur = ((X>>29)&1)*2 + ((X>>28)&1);

    bug(cur);

    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, 6969692);
    bug(SZ(rar));
    pii p = decode(1000000000);
    bug(SZ(rar));
//    encode(3, 3);
//    pii p = decode(3);
    bug(p.f, p.s);
}
#endif

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 1752 KB Output is correct
2 Correct 121 ms 1704 KB Output is correct
3 Correct 135 ms 1708 KB Output is correct
4 Correct 114 ms 1668 KB Output is correct
5 Correct 103 ms 1708 KB Output is correct
6 Correct 347 ms 1756 KB Output is correct
7 Correct 681 ms 1800 KB Output is correct

Subtask #2
59.00003 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 954 ms 1708 KB Output is partially correct
2 Partially correct 461 ms 1664 KB Output is partially correct
3 Partially correct 353 ms 1744 KB Output is partially correct
4 Partially correct 897 ms 1676 KB Output is partially correct
5 Partially correct 721 ms 1784 KB Output is partially correct
6 Partially correct 681 ms 1720 KB Output is partially correct
7 Partially correct 2012 ms 1740 KB Output is partially correct
8 Partially correct 3326 ms 2048 KB Output is partially correct
9 Partially correct 2828 ms 1908 KB Output is partially correct
10 Partially correct 2796 ms 1996 KB Output is partially correct
11 Partially correct 3066 ms 2028 KB Output is partially correct
12 Partially correct 3002 ms 1884 KB Output is partially correct
13 Partially correct 2950 ms 1888 KB Output is partially correct
14 Partially correct 2595 ms 2060 KB Output is partially correct
15 Partially correct 1516 ms 1780 KB Output is partially correct
16 Partially correct 3248 ms 1744 KB Output is partially correct
17 Partially correct 829 ms 1748 KB Output is partially correct
18 Correct 784 ms 1748 KB Output is correct
19 Partially correct 870 ms 1840 KB Output is partially correct
20 Correct 714 ms 1740 KB Output is correct
21 Correct 800 ms 1784 KB Output is correct
22 Partially correct 793 ms 1976 KB Output is partially correct
23 Partially correct 1158 ms 1836 KB Output is partially correct
24 Correct 113 ms 1780 KB Output is correct
25 Correct 98 ms 1664 KB Output is correct
26 Correct 158 ms 1776 KB Output is correct
27 Correct 110 ms 1664 KB Output is correct
28 Correct 70 ms 1708 KB Output is correct
29 Correct 290 ms 1780 KB Output is correct
30 Correct 825 ms 1672 KB Output is correct