oj.uz

Submission #1050618

# Submission time Handle Problem Language Result Execution time Memory
1050618 2024-08-09T11:54:06 Z That_Salamander Flight to the Ford (BOI22_communication) C++17
0 / 100
 2378 ms 3224 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 = max(1, 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 = max(currLength / 4, 1);

        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 Incorrect 2 ms 588 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 454 ms 2724 KB Output is partially correct
2 Partially correct 194 ms 2716 KB Output is partially correct
3 Partially correct 281 ms 2844 KB Output is partially correct
4 Partially correct 531 ms 2924 KB Output is partially correct
5 Partially correct 495 ms 2724 KB Output is partially correct
6 Partially correct 379 ms 2720 KB Output is partially correct
7 Partially correct 1414 ms 2784 KB Output is partially correct
8 Partially correct 2378 ms 3224 KB Output is partially correct
9 Partially correct 2058 ms 2948 KB Output is partially correct
10 Partially correct 2051 ms 3156 KB Output is partially correct
11 Partially correct 1976 ms 2928 KB Output is partially correct
12 Partially correct 2090 ms 2848 KB Output is partially correct
13 Partially correct 2001 ms 3096 KB Output is partially correct
14 Partially correct 1644 ms 3108 KB Output is partially correct
15 Partially correct 972 ms 3036 KB Output is partially correct
16 Partially correct 2029 ms 3024 KB Output is partially correct
17 Partially correct 502 ms 2864 KB Output is partially correct
18 Partially correct 535 ms 2784 KB Output is partially correct
19 Partially correct 530 ms 2864 KB Output is partially correct
20 Partially correct 509 ms 2788 KB Output is partially correct
21 Partially correct 568 ms 2780 KB Output is partially correct
22 Partially correct 600 ms 2808 KB Output is partially correct
23 Partially correct 964 ms 2868 KB Output is partially correct
24 Incorrect 2 ms 332 KB Not correct
25 Halted 0 ms 0 KB -