Submission #654577

#	Time	Username	Problem	Language	Result	Execution time	Memory
654577		Lobo	Flight to the Ford (BOI22_communication)	C++17	15 / 100	36 ms	1864 KiB

communication

#include"communication.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

//
// --- Sample implementation for the task communication ---
//
// To compile this program with the sample grader, place:
//     communication.h communication_sample.cpp sample_grader.cpp
// in a single folder, then open the terminal in this directory (right-click onto an empty spot in the directory,
// left click on "Open in terminal") and enter e.g.:
//     g++ -std=c++17 communication_sample.cpp sample_grader.cpp
// in this folder. This will create a file a.out in the current directory which you can execute from the terminal
// as ./a.out
// See task statement or sample_grader.cpp for the input specification
//

vector<pair<int,int>> join(vector<pair<int,int>> v1, vector<pair<int,int>> v2) {
    vector<pair<int,int>> v;
    for(auto x : v1) v.pb(x);
    for(auto x : v2) v.pb(x);
    return v;
}
void encode(int N, int X) {
    vector<pair<int,int>> vec,vqr; vec.pb(mp(1,N));
    int sz = N;
    while(sz >= 4) {
        vector<pair<int,int>> p1,p2,p3,p4;
        for(auto x : vec) sz+= x.sc-x.fr+1;
        int sz1 = sz/4; sz-= sz1;
        int sz2 = sz/3; sz-= sz2;
        int sz3 = sz/2; sz-= sz3;
        int sz4 = sz;

        while(vec.size() && sz1 != 0) {
            int l = vec.back().fr;
            int r = vec.back().sc;
            vec.pop_back();
            int l1 = max(l,r+1-sz1);
            p1.pb(mp(l1,r));
            sz1-= (r-l1+1);
            if(l1 != l) vec.pb(mp(l,l1-1));
        }
        while(vec.size() && sz2 != 0) {
            int l = vec.back().fr;
            int r = vec.back().sc;
            vec.pop_back();
            int l1 = max(l,r+1-sz2);
            p2.pb(mp(l1,r));
            sz2-= (r-l1+1);
            if(l1 != l) vec.pb(mp(l,l1-1));
        }
        while(vec.size() && sz3 != 0) {
            int l = vec.back().fr;
            int r = vec.back().sc;
            vec.pop_back();
            int l1 = max(l,r+1-sz3);
            p3.pb(mp(l1,r));
            sz3-= (r-l1+1);
            if(l1 != l) vec.pb(mp(l,l1-1));
        }
        p4 = vec;
        vec.clear();
        int ans1 = 0;
        // p1 p2 / p3 p4
        vqr = join(p1,p2);
        for(auto x : vqr) if(x.fr <= X && x.sc >= X) ans1 = 1;
        ans1 = send(ans1);
        int ans2 = 0;
        // p1 p3 / p2 p4
        vqr = join(p1,p3);
        for(auto x : vqr) if(x.fr <= X && x.sc >= X) ans2 = 1;
        ans2 = send(ans2);

        if(ans1 == 0 && ans2 == 0) p1.clear();
        if(ans1 == 0 && ans2 == 1) p2.clear();
        if(ans1 == 1 && ans2 == 0) p3.clear();
        if(ans1 == 1 && ans2 == 1) p4.clear();

        vec.clear();
        for(auto x : p1) vec.pb(x);
        for(auto x : p2) vec.pb(x);
        for(auto x : p3) vec.pb(x);
        for(auto x : p4) vec.pb(x);
        sz = 0;
        for(auto x : vec) sz+= x.sc-x.fr+1;
    }
    vector<pair<int,int>> vc1;
    for(auto x : vec) {
        for(int i = x.fr; i <= x.sc; i++) vc1.pb(mp(i,i));
    }
    vec = vc1;
    int ans1 = 0;
    // 0 / 1 2
    vqr = {vec[0]};
    for(auto x : vqr) if(x.fr <= X && x.sc >= X) ans1 = 1;
    ans1 = send(ans1);

    if(ans1 == 0) {
        // I have 0
        int ans2 = 0;
        // 0 | 1 2
        vqr = {vec[0]};
        for(auto x : vqr) if(x.fr <= X && x.sc >= X) ans2 = 1;
        ans2 = send(ans2);
        if(ans2 == 0) {
            // I take 0 off
            // return {vec[1],vec[2]};
        }
        else {
            // I have 1 2
            int ans3 = 0;
            // 1 | 0 2
            vqr = {vec[1]};
            for(auto x : vqr) if(x.fr <= X && x.sc >= X) ans3 = 1;
            ans3 = send(ans3);
            if(ans3 == 0) {
                // I take 1 off
                // return {vec[0],vec[2]};
            }
            else {
                // I take 2 off
                // return {vec[0],vec[1]};
            }
        }
    }
    else {
        // I have 1 2
        int ans2 = 0;
        // 1 | 0 2
        vqr = {vec[1]};
        for(auto x : vqr) if(x.fr <= X && x.sc >= X) ans2 = 1;
        ans2 = send(ans2);
        if(ans2 == 0) {
            // I take 1 off
            // return {vec[0],vec[2]};
        }
        else {
            // I take 2 off
            // return {vec[0],vec[1]};
        }

    }
}

std::pair<int, int> decode(int N) {
    vector<int> vec;
    for(int i = 1; i <= N; i++) vec.pb(i);
    vector<int> vqr;
    while(vec.size() >= 4) {
        vector<int> p1,p2,p3,p4;
        int sz = vec.size();
        int sz1 = sz/4; sz-= sz1;
        int sz2 = sz/3; sz-= sz2;
        int sz3 = sz/3; sz-= sz3;
        int sz4 = sz;

        for(int i = 0; i < sz1; i++) p1.pb(vec[i]);
        for(int i = sz1; i < sz2; i++) p2.pb(vec[i]);
        for(int i = sz2; i < sz3; i++) p3.pb(vec[i]);
        for(int i = sz3; i < sz4; i++) p4.pb(vec[i]);

        int ans1 = receive();
        int ans2 = receive();

        if(ans1 == 0 && ans2 == 0) p1.clear();
        if(ans1 == 0 && ans2 == 1) p2.clear();
        if(ans1 == 1 && ans2 == 0) p3.clear();
        if(ans1 == 1 && ans2 == 1) p4.clear();

        vec.clear();
        for(auto x : p1) vec.pb(x);
        for(auto x : p2) vec.pb(x);
        for(auto x : p3) vec.pb(x);
        for(auto x : p4) vec.pb(x);
    }
    
    int ans1 = receive();

    if(ans1 == 0) {
        // I have 0
        int ans2 = receive();
        if(ans2 == 0) {
            // I take 0 off
            return {vec[1],vec[2]};
        }
        else {
            // I have 1 2
            int ans3 = receive();
            if(ans3 == 0) {
                // I take 1 off
                return {vec[0],vec[2]};
            }
            else {
                // I take 2 off
                return {vec[0],vec[1]};
            }
        }
    }
    else {
        // I have 1 2
        int ans2 = receive();
        if(ans2 == 0) {
            // I take 1 off
            return {vec[0],vec[2]};
        }
        else {
            // I take 2 off
            return {vec[0],vec[1]};
        }

    }
}

Compilation message (stderr)

communication.cpp: In function 'void encode(int, int)':
communication.cpp:42:13: warning: unused variable 'sz4' [-Wunused-variable]
   42 |         int sz4 = sz;
      |             ^~~

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