Submission #1050621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050621		That_Salamander	Flight to the Ford (BOI22_communication)	C++17	74 / 100	2410 ms	3240 KiB

communication

#include <bits/stdc++.h>

#include "communication.h"

using namespace std;

int answer[4][4] = {{0, 0, 0, 0}, {0, 1, 1, 0}, {1, 0, 0, 1}, {1, 1, 1, 1}};

int corruptible(int* a, int* b, int size) {
    bool canCorrupt = true;
    for (int i = 0; i < size; i++) {
        if (a[i] != b[i]) {
            if (!canCorrupt) return false;
            canCorrupt = false;
        } else {
            canCorrupt = true;
        }
    }

    return true;
}

struct Tracker {
    vector<pair<int, int>> ranges;

    Tracker(int n) {
        ranges.emplace_back(1, n);
    }

    int totalLength() {
        int res = 0;
        for (auto& p: ranges) {
            res += p.second - p.first + 1;
        }
        return res;
    }

    int getIndex(int val) {
        int extra = 0;
        for (auto& p: ranges) {
            if (val >= p.first && val <= p.second) {
                return extra + (val - p.first);
            }
            extra += p.second - p.first + 1;
        }
        cerr << "ERROR" << endl;
        return 0;
    }

    int getElem(int idx) {
        for (auto& p: ranges) {
            int length = p.second - p.first + 1;
            if (idx < length) {
                return p.first + idx;
            } else {
                idx -= length;
            }
        }
        cerr << "ERROR" << endl;
        return 1;
    }

    void removeRange(int start, int end) {
        vector<pair<int, int>> res;
        for (auto& p: ranges) {
            if (p.second < start || p.first > end) {
                res.push_back(p);
            } else {
                if (start <= p.first && p.second <= end) continue;
                else if (start <= p.first) res.push_back({end + 1, p.second});
                else if (p.second <= end) res.push_back({p.first, start - 1});
                else {
                    res.push_back({p.first, start - 1});
                    res.push_back({end + 1, p.second});
                }
            }
        }

        ranges.swap(res);
    }

    void print() {
        for (auto& p: ranges) {
            cout << "[" << p.first << " " << p.second << "] ";
        }
        cout << endl;
    }
};

pair<int, int> sendNumber(int num) {
    int res[4];
    for (int i = 0; i < 4; i++) {
        res[i] = send(answer[num-1][i]);
    }

    int other = num;
    for (int i = 1; i <= 4; i++) {
        if (i == num) continue;
        if (corruptible(res, answer[i-1], 4)) {
            other = i;
            break;
        }
    }

    return {min(other, num), max(other, num)};
}

void encode(int n, int x) {
    Tracker tracker(n); 

    while (tracker.totalLength() > 2) {
        int currLength = tracker.totalLength();
        //cout << "Length = " << currLength << endl;
        int setLength = max(1, currLength / 4);

        int idx = tracker.getIndex(x);

        pair<int, int> recved = sendNumber(min(idx / setLength + 1, 4));

        for (int i = min(4, currLength); i >= 1; i--) {
            int start = tracker.getElem(setLength * (i - 1));
            int end = tracker.getElem(i == 4 ? currLength - 1 : setLength * i - 1);
            
            if (i != recved.first && i != recved.second) {
                //cout << "Removing range " << start << " " << end << endl;
                tracker.removeRange(start, end);
            }
        }
        //tracker.print();
    }
}

pair<int, int> decode(int n) {
    Tracker tracker(n);

    while (tracker.totalLength() > 2) {
        int res[4];
        for (int i = 0; i < 4; i++) {
            res[i] = receive();
        }

        vector<int> nums;
        for (int i = 0; i < 4; i++) {
            if (corruptible(res, answer[i], 4)) {
                nums.push_back(i + 1);
            }
        }
        nums.push_back(nums[0]);

        int a = nums[0];
        int b = nums[1];

        int currLength = tracker.totalLength();
        int setLength = max(currLength / 4, 1);

        for (int i = min(4, currLength); i >= 1; i--) {
            int start = tracker.getElem(setLength * (i - 1));
            int end = tracker.getElem(i == 4 ? currLength - 1 : setLength * i - 1);
            
            if (i != a && i != b) {
                //cout << "Removing range " << start << " " << end << endl;
                tracker.removeRange(start, end);
            }
        }

        //tracker.print();
    }

    return {tracker.getElem(0), tracker.getElem(1)};
}

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