Submission #993939

#	Time	Username	Problem	Language	Result	Execution time	Memory
993939		MarwenElarbi	Flight to the Ford (BOI22_communication)	C++17	0 / 100	274 ms	332 KiB

communication

#include <bits/stdc++.h>
#include<vector>
#include<cstdio>
#include<set>
#include<cstdlib>
#include<cstdarg>
#include<cassert>
#include"communication.h"

using namespace std;

#define fi first
#define se second
#define ll long long
#define pb push_back
const int nax=2e5+5;

/*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;
}*/

void encode(int N, int X){
    vector<pair<int,int>> v;
    v.pb({1,N});
    int a[4]={0,6,9,15};
    while(true){
        int value=0;
        for(auto j:v) value+=j.se-j.fi+1;
        if(value<=2) return;
        int sz[4]={value/4,value/4,value/4,value-3*(value/4)};
        vector<pair<int,int>> tab[4]; 
        for(int i=0;i<4;i++){
            int sum=0;
            for(int j=0;j<v.size();j++){
                sum+=v[j].se-v[j].fi+1;
                if(sum>=sz[i]){
                    int diff=sum-sz[i];
                    tab[i].pb({v[j].fi,v[j].se-diff});
                    v[j].fi=v[j].se-diff+1;
                    break;
                }else if(v[j].fi<=v[j].se){
                    tab[i].pb({v[j].fi,v[j].se});
                    v[j].fi=0;
                    v[j].se=-1;
                }
            }
        }
        v.clear();
        int ans;
        for(int i=0;i<4;i++){
            bool test=false;
            for(auto j:tab[i]){
                if(j.fi<=X&&X<=j.se) test=true;
            }
            if(test){
                ans=i;
                break;
            }
        }
        int cur=0;
        for(int i=0;i<4;i++){
            if(a[i]&(1<<i)) cur+=((send(1)&1)<<i);
            else  cur+=((send(0)&1)<<i);
        }
        for(int i=0;i<4;i++){
            int nab=cur^a[i];
            bool bits[4];
            for (int j = 0; j < 4; ++j)
            {
                bits[j]=( (nab&(1<<j)) ? 1 : 0 );
            }
            bool test=false;
            for (int j = 0; j < 3; ++j)
            {
                test|=(bits[j]==bits[j+1]&&bits[j]==1);
            }
            if(test) continue;
            for(auto j:tab[i]) v.pb(j);
        }
    }
}
std::pair<int, int> decode(int N){
    /*vector<vector<string>> tab(4 , vector<string>(8));
    tab[0]={"0000","0001","0010","0100","0101","1000","1001","1010"}; // 0000
    tab[1]={"0000","0001","0011","1000","1001","1011","1100","1101"}; // 1001
    tab[2]={"0010","0011","0100","0110","0111","1100","1110","1111"}; // 0110
    tab[3]={"0101","0110","0111","1010","1011","1101","1110","1111"}; // 1111
    set<string> st;
    for(int i=0;i<4;i++)
        for(auto u:tab[i]) st.insert(u);*/
    vector<pair<int,int>> v;
    v.pb({1,N});
    int a[4]={0,6,9,15};
    while(true){
        int value=0;
        for(auto j:v) value+=j.se-j.fi+1;
        if(value<=2){
            break;
        }
        int sz[4]={value/4,value/4,value/4,value-3*(value/4)};
        vector<pair<int,int>> tab[4]; 
        for(int i=0;i<4;i++){
            int sum=0;
            for(int j=0;j<v.size();j++){
                sum+=v[j].se-v[j].fi+1;
                if(sum>=sz[i]){
                    int diff=sum-sz[i];
                    tab[i].pb({v[j].fi,v[j].se-diff});
                    v[j].fi=v[j].se-diff+1;
                    break;
                }else if(v[j].fi<=v[j].se){
                    tab[i].pb({v[j].fi,v[j].se});
                    v[j].fi=0;
                    v[j].se=-1;
                }
            }
        }
        v.clear();
        vector<int> cur;
        for(int i=0;i<4;i++){
            cur.pb(receive());
        }
        for(int i=0;i<4;i++){
            if(cur[i]){
                for(auto j:tab[i]){
                    v.pb(j);
                } 
            }
        }
    }
    vector<int> ans;
    for(auto j:v){
        for(int i=j.fi;i<=j.se;i++) ans.pb(i);
    }
    if(ans.size()==1) return {ans[0],ans[0]};
    else return {ans[0],ans[1]};
}

/*int main()
{
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    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.");
}*/

Compilation message (stderr)

communication.cpp: In function 'void encode(int, int)':
communication.cpp:79:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |             for(int j=0;j<v.size();j++){
      |                         ~^~~~~~~~~
communication.cpp:94:13: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   94 |         int ans;
      |             ^~~
communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:149:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |             for(int j=0;j<v.size();j++){
      |                         ~^~~~~~~~~
communication.cpp:138:9: warning: unused variable 'a' [-Wunused-variable]
  138 |     int a[4]={0,6,9,15};
      |         ^

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