oj.uz

Submission #579871

# Submission time Handle Problem Language Result Execution time Memory
579871 2022-06-20T07:08:54 Z balbit Flight to the Ford (BOI22_communication) C++17
74 / 100
 3796 ms 1984 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;
}

int bigbad = 953183037;

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

//    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);
    ee.f ^= bigbad; ee.s ^= bigbad;
    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 100 ms 1760 KB Output is correct
2 Correct 88 ms 1668 KB Output is correct
3 Correct 158 ms 1720 KB Output is correct
4 Correct 89 ms 1692 KB Output is correct
5 Correct 90 ms 1764 KB Output is correct
6 Correct 302 ms 1736 KB Output is correct
7 Correct 783 ms 1728 KB Output is correct

Subtask #2
59.00003 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 568 ms 1796 KB Output is partially correct
2 Partially correct 316 ms 1676 KB Output is partially correct
3 Partially correct 492 ms 1696 KB Output is partially correct
4 Partially correct 824 ms 1840 KB Output is partially correct
5 Partially correct 511 ms 1664 KB Output is partially correct
6 Partially correct 575 ms 1692 KB Output is partially correct
7 Partially correct 2068 ms 1832 KB Output is partially correct
8 Partially correct 3067 ms 1968 KB Output is partially correct
9 Partially correct 2616 ms 1888 KB Output is partially correct
10 Partially correct 2429 ms 1900 KB Output is partially correct
11 Partially correct 2514 ms 1832 KB Output is partially correct
12 Partially correct 2717 ms 1880 KB Output is partially correct
13 Partially correct 2764 ms 1984 KB Output is partially correct
14 Partially correct 2989 ms 1900 KB Output is partially correct
15 Partially correct 1376 ms 1836 KB Output is partially correct
16 Partially correct 3796 ms 1800 KB Output is partially correct
17 Partially correct 898 ms 1880 KB Output is partially correct
18 Correct 760 ms 1796 KB Output is correct
19 Partially correct 706 ms 1820 KB Output is partially correct
20 Correct 766 ms 1920 KB Output is correct
21 Correct 659 ms 1828 KB Output is correct
22 Partially correct 761 ms 1880 KB Output is partially correct
23 Partially correct 1372 ms 1736 KB Output is partially correct
24 Correct 70 ms 1668 KB Output is correct
25 Correct 138 ms 1820 KB Output is correct
26 Correct 153 ms 1676 KB Output is correct
27 Correct 72 ms 1700 KB Output is correct
28 Correct 89 ms 1720 KB Output is correct
29 Correct 304 ms 1744 KB Output is correct
30 Correct 584 ms 1668 KB Output is correct