oj.uz

Submission #601611

# Submission time Handle Problem Language Result Execution time Memory
601611 2022-07-22T08:38:10 Z 반딧불(#8472) Flight to the Ford (BOI22_communication) C++17
0 / 100
 467 ms 248 KB 
#include "communication.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<int> vec;
int mySend(int x){
    vec.push_back(send(x));
    return vec.back();
}

int getBack(int A, int B, int C){
    return vector<int> {0, 0, 1, 2, 2, 2, 1, 1} [A*4+B*2+C];
}

int anna(int X){
    vec.clear();
    if(X==0){
        int tmp = mySend(0);
        if(!tmp){
            tmp = mySend(0);
            if(tmp) mySend(1);
        }
        else mySend(0);
    }
    else if(X==1){
        int tmp = mySend(0);
        if(!tmp){
            tmp = mySend(0);
            if(tmp) mySend(0);
        }
        else mySend(1);
    }
    else{
        int tmp = mySend(1);
        if(tmp){
            tmp = mySend(1);
        }
        else mySend(1), mySend(0);
    }
    return getBack(vec[0], vec[1], vec.size() == 2 ? 0 : vec[2]);
}

void encode(int N, int X){
    X--;
    ll L = 0, R = N-1;
    srand(N);
    while(R-L>1){
        ll P = (L+L+R)/3, Q = (L+R+R)/3; /// [0, P], (P, Q], (Q, R]
        ll toSend = (X<=P ? 0 : X<=Q ? 1 : 2);
        toSend = (toSend + rand()) % 3;
        ll gone = anna(toSend);
//        printf("Gone: %d\n", gone);
        if(gone == 0) R = Q;
        else if(gone == 1) R -= P+1, X -= P+1;
        else if(toSend == 2) R -= Q+1, R += P+1, X -= Q+1;
        else{
            X += R+1, X -= Q+1;
            R -= Q+1, R += P+1;
        }
    }
}

struct dat{
    ll lim, a, b; /// lim ���ϸ� +a, �ʰ��� +b
    dat(){}
    dat(ll lim, ll a, ll b): lim(lim), a(a), b(b){}

    ll calc(ll x){
        return (x<=lim) ? x+a : x+b;
    }
};

pair<int, int> decode(int N){
    ll L = 0, R = N-1;
    vector<dat> vec;
    srand(N);
    while(R-L>1){
        ll P = (L+L+R)/3, Q = (L+R+R)/3; /// [0, P], (P, Q], (Q, R]
        ll A = receive();
        ll B = receive();
        ll C = 0;
        if(A==0 && B==1) C = receive();
        ll gone = getBack(A, B, C);
        gone = (gone + 333333333 - rand()) % 3;
//        printf("Received: %d\n", gone);
        if(gone == 0) R = Q;
        else if(gone == 1) vec.push_back(dat(LLONG_MAX, P+1, P+1)), R -= P+1;
        else{
            vec.push_back(dat(R-Q-1, Q+1, -R+Q));
            R -= Q+1, R += P+1;
        }
    }
    pair<int, int> ret (L, R);
    for(int i=(int)vec.size()-1; i>=0; i--){
        ret.first = vec[i].calc(ret.first);
        ret.second = vec[i].calc(ret.second);
    }
    ret.first++, ret.second++;
    return ret;
}

Subtask #1
0.0 / 15.0

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

Subtask #2
0.0 / 85.0

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