Submission #654468

#	Time	Username	Problem	Language	Result	Execution time	Memory
654468		AlperenT	Flight to the Ford (BOI22_communication)	C++17	74 / 100	3809 ms	2064 KiB

communication

#include <bits/stdc++.h>
#include "communication.h"

using namespace std;

//
// --- 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
//

struct Seg{
    int l, r;

    bool operator < (const Seg &sc) const{
        if(l == sc.l) return r < sc.r;
        else return l < sc.l;
    }
};

vector<Seg> merge(vector<Seg> a, vector<Seg> b){
    for(auto seg : b) a.push_back(seg);
    return a;
}

vector<Seg> fix(vector<Seg> vec){
    sort(vec.begin(), vec.end());

    vector<Seg> ans;

    for(auto seg : vec){
        if(ans.empty() || seg.l != ans.back().r + 1) ans.push_back(seg);
        else ans.back().r = seg.r;
    }

    return ans;
}

bool isin(vector<Seg> vec, int x){
    for(auto seg : vec) if(x >= seg.l && x <= seg.r) return true;
    return false;
}

int len(vector<Seg> vec){
    int ans = 0;

    for(auto seg : vec) ans += seg.r - seg.l + 1;

    return ans;
}

bool isgood(string str){
    if(str[0] == '0' && str[1] == '0') return false;
    else if(str[1] == '0' && str[2] == '0') return false;
    else if(str[2] == '0' && str[3] == '0') return false;
    else return true;
}

vector<int> tokeep(string str){
    vector<int> ans;

    string truth;

    // 1 0 0 0

    truth += str[0] == '1' ? '1' : '0';
    truth += str[1] == '0' ? '1' : '0';
    truth += str[2] == '0' ? '1' : '0';
    truth += str[3] == '0' ? '1' : '0';

    if(isgood(truth)) ans.push_back(0);

    // 0 1 0 0

    truth = "";

    truth += str[0] == '0' ? '1' : '0';
    truth += str[1] == '1' ? '1' : '0';
    truth += str[2] == '1' ? '1' : '0';
    truth += str[3] == '0' ? '1' : '0';

    if(isgood(truth)) ans.push_back(1);

    // 0 0 1 0

    truth = "";

    truth += str[0] == '0' ? '1' : '0';
    truth += str[1] == '0' ? '1' : '0';
    truth += str[2] == '0' ? '1' : '0';
    truth += str[3] == '1' ? '1' : '0';

    if(isgood(truth)) ans.push_back(2);

    // 0 0 0 1

    truth = "";

    truth += str[0] == '1' ? '1' : '0';
    truth += str[1] == '1' ? '1' : '0';
    truth += str[2] == '1' ? '1' : '0';
    truth += str[3] == '1' ? '1' : '0';

    if(isgood(truth)) ans.push_back(3);

    return ans;
}

void encode(int n, int x) {
    vector<Seg> segments = {{1, n}};

    while(len(segments) > 3){
        vector<Seg> parts[4];

        int req = len(segments) / 4;

        int cur = 0, cursum = 0;

        for(int i = 0; i < segments.size(); i++){
            if(cur == 3 || cursum + (segments[i].r - segments[i].l + 1) <= req){
                parts[cur].push_back(segments[i]);
                cursum += (segments[i].r - segments[i].l + 1);
            }
            else{
                if(cursum < req){
                    parts[cur].push_back({segments[i].l, segments[i].l + (req - cursum) - 1});
                    segments[i].l = segments[i].l + (req - cursum);
                }

                cur++, cursum = 0;
                i--;
            }
        }

        string answers;

        answers += '0' + (send(isin(parts[0], x) || isin(parts[3], x)));
        answers += '0' + (send(isin(parts[1], x) || isin(parts[3], x)));
        answers += '0' + (send(isin(parts[1], x) || isin(parts[3], x)));
        answers += '0' + (send(isin(parts[2], x) || isin(parts[3], x)));

        vector<int> keep = tokeep(answers);

        assert(keep.size() == 2);

        segments = merge(parts[keep[0]], parts[keep[1]]);

        segments = fix(segments);
    }

    if(len(segments) == 3){
        vector<int> nums(3);

        if(segments.size() == 1){
            nums[0] = segments[0].l;
            nums[1] = segments[0].l + 1;
            nums[2] = segments[0].l + 2;
        }
        else if(segments.size() == 2){
            if(segments[0].l == segments[0].r){
                nums[0] = segments[0].l;
                nums[1] = segments[1].l;
                nums[2] = segments[1].l + 1;
            }
            else{
                nums[0] = segments[0].l;
                nums[1] = segments[0].l + 1;
                nums[2] = segments[1].l;
            }
        }
        else{
            nums[0] = segments[0].l;
            nums[1] = segments[1].l;
            nums[2] = segments[2].l;
        }

        send(nums[0] == x || nums[2] == x);
        send(nums[1] == x || nums[2] == x);
        send(nums[1] == x || nums[2] == x);
        send(nums[2] == x);
    }
}

pair<int, int> decode(int n) {
    vector<Seg> segments = {{1, n}};

    while(len(segments) > 3){
        vector<Seg> parts[4];

        int req = len(segments) / 4;

        int cur = 0, cursum = 0;

        for(int i = 0; i < segments.size(); i++){
            if(cur == 3 || cursum + (segments[i].r - segments[i].l + 1) <= req){
                parts[cur].push_back(segments[i]);
                cursum += (segments[i].r - segments[i].l + 1);
            }
            else{
                if(cursum < req){
                    parts[cur].push_back({segments[i].l, segments[i].l + (req - cursum) - 1});
                    segments[i].l = segments[i].l + (req - cursum);
                }

                cur++, cursum = 0;
                i--;
            }
        }

        string answers;

        answers += '0' + receive();
        answers += '0' + receive();
        answers += '0' + receive();
        answers += '0' + receive();

        vector<int> keep = tokeep(answers);

        assert(keep.size() == 2);

        segments = merge(parts[keep[0]], parts[keep[1]]);

        segments = fix(segments);
    }

    if(len(segments) == 1) return {segments[0].l, segments[0].l};
    else if(len(segments) == 2){
        if(segments.size() == 1) return {segments[0].l, segments[0].l + 1};
        else{
            return {segments[0].l, segments[1].l};
        }
    }
    if(len(segments) == 3){
        vector<int> nums(3);

        if(segments.size() == 1){
            nums[0] = segments[0].l;
            nums[1] = segments[0].l + 1;
            nums[2] = segments[0].l + 2;
        }
        else if(segments.size() == 2){
            if(segments[0].l == segments[0].r){
                nums[0] = segments[0].l;
                nums[1] = segments[1].l;
                nums[2] = segments[1].l + 1;
            }
            else{
                nums[0] = segments[0].l;
                nums[1] = segments[0].l + 1;
                nums[2] = segments[1].l;
            }
        }
        else{
            nums[0] = segments[0].l;
            nums[1] = segments[1].l;
            nums[2] = segments[2].l;
        }

        string answers;

        answers += '0' + receive();
        answers += '0' + receive();
        answers += '0' + receive();
        answers += '0' + receive();

        vector<int> ans;

        string truth;

        // 1 0 0

        truth += answers[0] == '1' ? '1' : '0';
        truth += answers[1] == '0' ? '1' : '0';
        truth += answers[2] == '0' ? '1' : '0';
        truth += answers[3] == '0' ? '1' : '0';

        if(isgood(truth)) ans.push_back(0);

        // 0 1 0

        truth = "";

        truth += answers[0] == '0' ? '1' : '0';
        truth += answers[1] == '1' ? '1' : '0';
        truth += answers[2] == '1' ? '1' : '0';
        truth += answers[3] == '0' ? '1' : '0';

        if(isgood(truth)) ans.push_back(1);

        // 0 0 1

        truth = "";

        truth += answers[0] == '1' ? '1' : '0';
        truth += answers[1] == '1' ? '1' : '0';
        truth += answers[2] == '1' ? '1' : '0';
        truth += answers[3] == '1' ? '1' : '0';

        if(isgood(truth)) ans.push_back(2);

        if(ans.size() == 1) return {nums[ans[0]], nums[ans[0]]};
        else return {nums[ans[0]], nums[ans[1]]};
    }
}

Compilation message (stderr)

communication.cpp: In function 'void encode(int, int)':
communication.cpp:126:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |         for(int i = 0; i < segments.size(); i++){
      |                        ~~^~~~~~~~~~~~~~~~~
communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:201:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |         for(int i = 0; i < segments.size(); i++){
      |                        ~~^~~~~~~~~~~~~~~~~
communication.cpp:192:35: warning: control reaches end of non-void function [-Wreturn-type]
  192 |     vector<Seg> segments = {{1, n}};
      |                                   ^

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