oj.uz

Submission #1050615

# Submission time Handle Problem Language Result Execution time Memory
1050615 2024-08-09T11:52:54 Z That_Salamander Flight to the Ford (BOI22_communication) C++17
0 / 100
 2258 ms 3256 KB 
#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 = currLength / 4;

        int idx = tracker.getIndex(x);

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

        for (int i = 4; 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 = currLength / 4;

        for (int i = 4; 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
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 483 ms 2728 KB Output is partially correct
2 Partially correct 197 ms 2716 KB Output is partially correct
3 Partially correct 296 ms 2736 KB Output is partially correct
4 Partially correct 520 ms 2836 KB Output is partially correct
5 Partially correct 393 ms 2720 KB Output is partially correct
6 Partially correct 366 ms 2740 KB Output is partially correct
7 Partially correct 1397 ms 2972 KB Output is partially correct
8 Partially correct 2258 ms 2916 KB Output is partially correct
9 Partially correct 1922 ms 2980 KB Output is partially correct
10 Partially correct 1838 ms 2864 KB Output is partially correct
11 Partially correct 1902 ms 3256 KB Output is partially correct
12 Partially correct 1794 ms 3104 KB Output is partially correct
13 Partially correct 1729 ms 3144 KB Output is partially correct
14 Partially correct 1942 ms 2952 KB Output is partially correct
15 Partially correct 1036 ms 2968 KB Output is partially correct
16 Partially correct 2218 ms 2780 KB Output is partially correct
17 Partially correct 544 ms 2984 KB Output is partially correct
18 Partially correct 524 ms 2976 KB Output is partially correct
19 Partially correct 537 ms 2808 KB Output is partially correct
20 Partially correct 530 ms 2796 KB Output is partially correct
21 Partially correct 517 ms 2804 KB Output is partially correct
22 Partially correct 533 ms 2888 KB Output is partially correct
23 Partially correct 845 ms 2820 KB Output is partially correct
24 Runtime error 1 ms 332 KB Execution killed with signal 8
25 Halted 0 ms 0 KB -