Submission #654669

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

communication

#include <bits/stdc++.h>
#include "communication.h"
 
using namespace std;
 
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;
        }
 
        if(send(nums[0] == x) || send(nums[0] == x)){
            send(nums[1] == 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;
        }
 
        if(receive() || receive()){
            if(receive()) return {nums[0], nums[1]};
            else return {nums[0], nums[2]};
        }
        else return {nums[1], nums[2]};
    }
}

Compilation message (stderr)

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

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