oj.uz

Submission #654669

# Submission time Handle Problem Language Result Execution time Memory
654669 2022-11-01T07:29:18 Z AlperenT Flight to the Ford (BOI22_communication) C++17
74 / 100
 3682 ms 2056 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1772 KB Output is correct
2 Correct 11 ms 1760 KB Output is correct
3 Correct 16 ms 1672 KB Output is correct
4 Correct 10 ms 1804 KB Output is correct
5 Correct 10 ms 1748 KB Output is correct
6 Correct 15 ms 1796 KB Output is correct
7 Correct 37 ms 1600 KB Output is correct

Subtask #2
59.00003 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 915 ms 1860 KB Output is partially correct
2 Partially correct 300 ms 1720 KB Output is partially correct
3 Partially correct 588 ms 1664 KB Output is partially correct
4 Partially correct 878 ms 1824 KB Output is partially correct
5 Partially correct 746 ms 1664 KB Output is partially correct
6 Partially correct 625 ms 1704 KB Output is partially correct
7 Partially correct 2647 ms 1792 KB Output is partially correct
8 Partially correct 3564 ms 2056 KB Output is partially correct
9 Partially correct 3164 ms 1880 KB Output is partially correct
10 Partially correct 2921 ms 1896 KB Output is partially correct
11 Partially correct 3384 ms 1884 KB Output is partially correct
12 Partially correct 3294 ms 1984 KB Output is partially correct
13 Partially correct 3185 ms 1796 KB Output is partially correct
14 Partially correct 3211 ms 1940 KB Output is partially correct
15 Partially correct 1671 ms 1860 KB Output is partially correct
16 Partially correct 3682 ms 1724 KB Output is partially correct
17 Partially correct 922 ms 1728 KB Output is partially correct
18 Partially correct 916 ms 1788 KB Output is partially correct
19 Partially correct 900 ms 1868 KB Output is partially correct
20 Partially correct 950 ms 1792 KB Output is partially correct
21 Partially correct 848 ms 1824 KB Output is partially correct
22 Partially correct 922 ms 1844 KB Output is partially correct
23 Partially correct 1404 ms 1852 KB Output is partially correct
24 Correct 9 ms 1784 KB Output is correct
25 Correct 13 ms 1760 KB Output is correct
26 Correct 14 ms 1724 KB Output is correct
27 Correct 8 ms 1748 KB Output is correct
28 Correct 10 ms 1720 KB Output is correct
29 Correct 15 ms 1800 KB Output is correct
30 Correct 31 ms 1716 KB Output is correct