oj.uz

Submission #579854

# Submission time Handle Problem Language Result Execution time Memory
579854 2022-06-20T05:59:28 Z balbit Flight to the Ford (BOI22_communication) C++17
15 / 100
 51 ms 1796 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);
}

void encode(signed N, signed X) {
    build();
    --X;
    pii pp = trysend(X);
}

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

    pii ee = eat4();
    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);

    rar.clear(); canflip = 1;

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

Compilation message

communication.cpp: In function 'void encode(int, int)':
communication.cpp:111:9: warning: variable 'pp' set but not used [-Wunused-but-set-variable]
  111 |     pii pp = trysend(X);
      |         ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1772 KB Output is correct
2 Correct 19 ms 1760 KB Output is correct
3 Correct 12 ms 1736 KB Output is correct
4 Correct 11 ms 1712 KB Output is correct
5 Correct 11 ms 1700 KB Output is correct
6 Correct 27 ms 1796 KB Output is correct
7 Correct 51 ms 1668 KB Output is correct

Subtask #2
0.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 456 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -