제출 #1306636

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306636		Davdav1232	Flight to the Ford (BOI22_communication)	C++20	15 / 100	134 ms	3036 KiB

communication

#include"communication.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<pii> vii;




// void __attribute__((noreturn)) __attribute__((format(printf, 1, 2))) result(const char *msg, ...)
// {
//     va_list args;
//     va_start(args, msg);
//     vfprintf(stdout, msg, args);
//     fprintf(stdout, "\n");
//     va_end(args);
//     exit(0);
// }

// namespace
// {
//     enum { ENCODE, DECODE } current_phase;
//     int N, X;
//     vector<int> signals;
//     size_t cursor = 0;
//     bool flipped = false;
// }

// int send(int s)
// {
//     if(current_phase == DECODE or (s != 0 and s != 1))
//         result("Invalid send.");

//     printf("send(%d) -> ", s); fflush(stdout);
//     int answer;
//     if(scanf("%d", &answer) != 1 or (answer != 0 and answer != 1))
//         result("Invalid reply to send.");

//     bool flipped_now = (s != answer);
//     if(flipped and flipped_now)
//         result("Invalid reply to send");
//     flipped = flipped_now;

//     signals.push_back(answer);
//     if(signals.size() > (size_t) 250)
//         result("Looks (and smells) fishy.");
//     return signals.back();
// }

// int receive()
// {
//     if(current_phase == ENCODE)  result("Invalid receive.");
//     if(cursor >= signals.size()) result("Assistant waiting for Godot.");
//     int r = signals[cursor++];
//     printf("receive() -> %d\n", r);
//     return r;
// }


bool init=0;
vi fib={0, 1};

int find_fib(int len, vi x){
    if(len==0) return 0;
    int ans=0;
    if(x[len-1]==1){
        ans+=fib[len+1];
    }
    x.pop_back();
    return ans+find_fib(len-1, x);
}

vi gen_fib(int len, int x){
    vi ans;
    while(len){
        if(x>=fib[len+1]){
            ans.push_back(1);
            x-=fib[len+1];
        }
        else ans.push_back(0);
        len--;
    }
    return ans;
}

void encode(int n, int x){
    if(!init){
        init=1;
        int sz=2;
        while(fib[sz-1]<(1<<30)){
            fib.push_back(fib[sz-1]+fib[sz-2]);
            sz++;
        }
    }
    x--;
    if(n==5){
        int a=0, b=0;
        if(x&2) a=1;
        if(x&1) b=1;
        int c=send(a);
        int d=send(b);
        //it knows it isn't (1-c)*2+1-d
        if(3-2*c-d>x){
            encode(4, x+1);
        }
        else{
            encode(4, x);
        }
        return;
    }
    if(n>3){
        int a=1;
        int l=0;
        while(a<n){
            a*=2;
            l++;
        }
        //I need to send them the thing
        vi out(l, 0);
        for(int i=0; i<l; i++){
            if((1<<(l-i-1))&x) out[i]=1;
        }
        vi err(l);
        for(int i=0; i<l; i++) err[i]=(send(out[i])!=out[i]);
        reverse(err.begin(), err.end());
        //Now I need to send out the error
        int new_x=find_fib(l, err);
        encode(fib[l+2], new_x+1);
        return;
    }
    if(x==0){
        send(0);
        send(0);
        send(0);
        send(0);
    }
    if(x==1){
        send(0);
        send(1);
        send(1);
        send(0);
    }
    if(x==2){
        send(1);
        send(0);
        send(0);
        send(1);
    }
}


pii decode(int n){
    if(!init){
        init=1;
        int sz=2;
        while(fib[sz-1]<(1<<30)){
            fib.push_back(fib[sz-1]+fib[sz-2]);
            sz++;
        }
    }
    if(n==5){
        int a=receive(), b=receive();
        int NOT=3-2*a-b;
        pii t=decode(4);
        t.first--;
        t.second--;
        if(t.first>=NOT) t.first++;
        if(t.second>=NOT) t.second++;
        return {t.first++, t.second++};
    }
    if(n>3){
        int a=1;
        int l=0;
        while(a<n){
            a*=2;
            l++;
        }
        vector<int> inp(l);
        for(int i=0; i<l; i++) inp[i]=receive();
        //I need to xor this with the real thing
        pii e=decode(fib[l+2]);
        e.first--;
        e.second--;

        pii pot={0, 0};
        for(int i=0; i<l; i++){
            if(inp[i]){
                pot.first+=1<<(l-i-1);
                pot.second+=1<<(l-i-1);
            }
        }
        //I need to xor the options
        vi f=gen_fib(l, e.first);
        vi s=gen_fib(l, e.second);
        for(int i=0; i<l; i++){
            if(f[i]){
                pot.first^=1<<(l-i-1);
            }
            if(s[i]){
                pot.second^=1<<(l-i-1);
            }
        }
        pot.first+=1;
        pot.second+=1;
        return pot;
    }
    int a, b, c, d;
    a=receive();
    b=receive();
    c=receive();
    d=receive();
    if(a==0 && b==1){
        //1 0 not possible
        return {2, 1};
    }
    if(a==1 && b==0){
        return {1, 3};
    }
    if(a==1 && b==1){
        return {2, 3};
    }
    if(c==1 && d==0){
        //1 0 not possible
        return {2, 1};
    }
    if(c==0 && d==1){
        return {1, 3};
    }
    if(c==1 && d==1){
        return {2, 3};
    }
    //now they are 0, 0 which means it can't be 0110
    return {1, 3};
    //a and b are 0. if I tried to send 1, that means
}









// int main()
// {
//     if(scanf("%d %d", &N, &X) != 2 or X < 1 or X > N)
//         result("Invalid input.");

//     current_phase = ENCODE;
//     encode(N, X);
//     current_phase = DECODE;
//     auto r = decode(N);

//     if(r.first < 1 or r.first > N or r.second < 1 or r.second > N)
//         result("Invalid answer.");

//     if(r.first == X or r.second == X)
//         result("Correct: %d signals sent.", (int) signals.size());
//     else
//         result("Wrong answer.");
// }

• Subtask 1: 15 / 15
• Subtask 2: 0 / 85