oj.uz

Submission #584055

# Submission time Handle Problem Language Result Execution time Memory
584055 2022-06-26T17:25:11 Z cheissmart Flight to the Ford (BOI22_communication) C++17
74 / 100
 3496 ms 2128 KB 
#include"communication.h"
#include <bits/stdc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

int aux[] = {0b0000, 0b1001, 0b0110, 0b1111};

vi get_bad(int x) {
    vi ans;
    for(int k = 0; k < 4; k++)
        if(x == aux[k])
            ans.PB(k);
    for(int i = 0; i < 4; i++) {
        int y = x ^ (1 << i);
        for(int k = 0; k < 4; k++)
            if(y == aux[k])
                ans.PB(k);
        for(int j = 0; j < i - 1; j++) {
            int z = y ^ (1 << j);
            for(int k = 0; k < 4; k++)
                if(z == aux[k])
                    ans.PB(k);
        }
    }
    vi bad;
    for(int i = 0; i < 4; i++)
        if(count(ALL(ans), i) == 0)
            bad.PB(i);
    return bad;
};

void encode(int n, int x) {
    x--;
    auto send_4 = [&] (int y) {
        assert(0 <= y && y < 4);
        int sent = 0;
        for(int i = 0; i < 4; i++)
            sent |= send(aux[y] >> i & 1) << i;

        return get_bad(sent);
    };
    function<void(int)> go = [&] (int m) { // [0, m);
        assert(x < m);
        if(m <= 4) {
            send_4(x);
            return;
        }
        int b = m / 2, a = b / 2, c = (b + m) / 2;
        int aux[] = {0, a, b, c, m};
        int which = 0;
        while(!(aux[which] <= x && x < aux[which + 1]))
            which++;
        vi bad = send_4(which);
        int new_m = m, new_x = x;

        for(int i = 0; i < 4; i++) {
            if(count(ALL(bad), i)) {
                new_m -= aux[i + 1] - aux[i];
                if(aux[i] < x) new_x -= aux[i + 1] - aux[i];
            }
        }

        x = new_x;
        go(new_m);
    };
    go(n);
}

pi decode(int n) {
    auto get_4 = [&] () {
        int x = 0;
        for(int i = 0; i < 4; i++)
            x |= receive() << i;
        return get_bad(x);
    };
    function<pi(int)> go = [&] (int m) -> pi { // [0, m);
        if(m <= 4) {
            vi bad = get_4(), good;
            for(int i = 0; i < m; i++)
                if(count(ALL(bad), i) == 0)
                    good.PB(i);
            while(SZ(good) < 2)
                good.PB(0);
            return {good[0], good[1]};
        }
        vi bad = get_4();
        int b = m / 2, a = b / 2, c = (b + m) / 2;
        int aux[] = {0, a, b, c, m}, new_m = m;
        for(int i = 0; i < 4; i++) {
            if(count(ALL(bad), i)) {
                new_m -= aux[i + 1] - aux[i];
            }
        }
        auto go_back = [&] (int x) -> int {
            for(int i = 0; i < 4; i++) {
                if(count(ALL(bad), i)) {
                    x += aux[i + 1] - aux[i];
                } else {
                    if(aux[i] <= x && x < aux[i + 1])
                        return x;
                }
            }
            throw;
        };
        auto[x, y] = go(new_m);
        return {go_back(x), go_back(y)};
    };
    auto[x, y] = go(n);
    return {x + 1, y + 1};
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1816 KB Output is correct
2 Correct 15 ms 1716 KB Output is correct
3 Correct 14 ms 1688 KB Output is correct
4 Correct 10 ms 1776 KB Output is correct
5 Correct 14 ms 1760 KB Output is correct
6 Correct 22 ms 1744 KB Output is correct
7 Correct 46 ms 1664 KB Output is correct

Subtask #2
59.00003 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 659 ms 1696 KB Output is partially correct
2 Partially correct 461 ms 1756 KB Output is partially correct
3 Partially correct 553 ms 1800 KB Output is partially correct
4 Partially correct 858 ms 1832 KB Output is partially correct
5 Partially correct 805 ms 1688 KB Output is partially correct
6 Partially correct 457 ms 1672 KB Output is partially correct
7 Partially correct 2130 ms 1884 KB Output is partially correct
8 Partially correct 3231 ms 2128 KB Output is partially correct
9 Partially correct 3078 ms 1980 KB Output is partially correct
10 Partially correct 3083 ms 1904 KB Output is partially correct
11 Partially correct 2955 ms 1904 KB Output is partially correct
12 Partially correct 3212 ms 1888 KB Output is partially correct
13 Partially correct 3158 ms 2128 KB Output is partially correct
14 Partially correct 3037 ms 1980 KB Output is partially correct
15 Partially correct 1626 ms 1816 KB Output is partially correct
16 Partially correct 3496 ms 1876 KB Output is partially correct
17 Partially correct 827 ms 1732 KB Output is partially correct
18 Partially correct 808 ms 1740 KB Output is partially correct
19 Partially correct 850 ms 1856 KB Output is partially correct
20 Partially correct 799 ms 1860 KB Output is partially correct
21 Partially correct 892 ms 1724 KB Output is partially correct
22 Partially correct 900 ms 1796 KB Output is partially correct
23 Partially correct 1330 ms 1812 KB Output is partially correct
24 Correct 10 ms 1732 KB Output is correct
25 Correct 14 ms 1892 KB Output is correct
26 Correct 17 ms 1772 KB Output is correct
27 Correct 13 ms 1620 KB Output is correct
28 Correct 13 ms 1664 KB Output is correct
29 Correct 26 ms 1744 KB Output is correct
30 Correct 45 ms 1728 KB Output is correct