oj.uz

Submission #579869

# Submission time Handle Problem Language Result Execution time Memory
579869 2022-06-20T07:02:57 Z balbit Flight to the Ford (BOI22_communication) C++17
0 / 100
 359 ms 200 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));
                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);
                }
                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>>1)&1)*2 + ((X>>0)&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
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 200 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 359 ms 200 KB Not correct
2 Halted 0 ms 0 KB -