oj.uz

Submission #829534

# Submission time Handle Problem Language Result Execution time Memory
829534 2023-08-18T12:13:30 Z QwertyPi Flight to the Ford (BOI22_communication) C++17
92 / 100
 2282 ms 2112 KB 
#include"communication.h"
#include <bits/stdc++.h>

using namespace std;

//
// --- Sample implementation for the task communication ---
//
// To compile this program with the sample grader, place:
//     communication.h communication_sample.cpp sample_grader.cpp
// in a single folder, then open the terminal in this directory (right-click onto an empty spot in the directory,
// left click on "Open in terminal") and enter e.g.:
//     g++ -std=c++17 communication_sample.cpp sample_grader.cpp
// in this folder. This will create a file a.out in the current directory which you can execute from the terminal
// as ./a.out
// See task statement or sample_grader.cpp for the input specification
//

void encode(int N, int X) {
    int B = __lg(N + 1) + 1; mt19937 rng; rng.seed(1337);
    vector<int> bits; for(int j = 0; j < B; j++) bits.push_back(j);
    for(int i = 0; i < B; i++) swap(bits[i], bits[rng() % (i + 1)]);
    vector<int> a; for(int j = 0; j < B; j++) a.push_back((X & (1 << j)) > 0);
    int prv = -1, prv_val = 0;
    while(bits.size() >= 2){
        int b1 = bits.back(); bits.pop_back();
        int b2 = bits.back(); bits.pop_back();

        int s1 = prv != -1 ? prv_val : send(a[b1]);
        int s2 = send(a[b2]);
        int s3 = send(a[b2]);

        prv = -1;
        if(s2 == s3){
            bits.push_back(b1);
            continue;
        }

        int s4 = send(a[b1]);
        if(s1 == s4){
            bits.push_back(b2);
        }else{
            bits.push_back(b1);
            prv = b1; prv_val = s4;
        }
    }
}

struct DSU{
    int dsu[71];
    void init(){
        for(int i = 0; i < 71; i++) dsu[i] = i;
    }
    int f(int x){ return x == dsu[x] ? x : dsu[x] = f(dsu[x]); }
    void g(int x, int y){ x = f(x), y = f(y); dsu[x] = y; }
} dsu;

void link(int u, int v, bool b){
    dsu.g(u * 2, v * 2 + b);
    dsu.g(u * 2 + 1, v * 2 + !b);
}

std::pair<int, int> decode(int N) {
    int B = __lg(N + 1) + 1; mt19937 rng; rng.seed(1337);
    vector<int> bits; for(int j = 0; j < B; j++) bits.push_back(j);
    for(int i = 0; i < B; i++) swap(bits[i], bits[rng() % (i + 1)]);
    vector<int> a;
    dsu.init();
    int prv = -1, prv_val = 0;
    while(bits.size() >= 2){
        int b1 = bits.back(); bits.pop_back();
        int b2 = bits.back(); bits.pop_back();

        int s1 = prv != -1 ? prv_val : receive();
        int s2 = receive();
        int s3 = receive();

        prv = -1;
        if(s2 == s3){
            link(b2, B, s2);
            bits.push_back(b1);
            continue;
        }

        int s4 = receive();

        if(s1 == s4){
            link(b1, B, s1);
            bits.push_back(b2);
        }else{
            link(b1, b2, s1 ^ s2 ^ 1);
            bits.push_back(b1);
            prv = b1; prv_val = s4;
        }
    }

    int sp = bits[0];
    vector<int> ans;
    for(int i = 0; i < 2; i++){
        int r = 0;
        for(int j = 0; j < B; j++){
            bool y = dsu.f(j * 2) == dsu.f(B * 2 + 1) || dsu.f(j * 2) == dsu.f(sp * 2 + (1 - i));
            r += (1 << j) * y;
        }
        ans.push_back(r);
    }
    if(ans[0] < 1 || ans[0] > N) ans[0] = 1;
    if(ans[1] < 1 || ans[1] > N) ans[1] = 1;
    return {ans[0], ans[1]};
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1688 KB Output is correct
2 Correct 10 ms 1736 KB Output is correct
3 Correct 16 ms 2100 KB Output is correct
4 Correct 8 ms 1720 KB Output is correct
5 Correct 10 ms 1688 KB Output is correct
6 Correct 24 ms 1756 KB Output is correct
7 Correct 47 ms 1760 KB Output is correct

Subtask #2
76.99997 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 437 ms 1772 KB Output is partially correct
2 Partially correct 195 ms 1812 KB Output is partially correct
3 Partially correct 265 ms 1776 KB Output is partially correct
4 Partially correct 527 ms 1716 KB Output is partially correct
5 Partially correct 388 ms 1768 KB Output is partially correct
6 Correct 364 ms 1668 KB Output is correct
7 Correct 1319 ms 1732 KB Output is correct
8 Correct 1915 ms 2112 KB Output is correct
9 Correct 1651 ms 1940 KB Output is correct
10 Correct 1777 ms 1988 KB Output is correct
11 Correct 1669 ms 1912 KB Output is correct
12 Correct 1784 ms 1928 KB Output is correct
13 Correct 1851 ms 1944 KB Output is correct
14 Correct 1857 ms 2020 KB Output is correct
15 Correct 982 ms 1824 KB Output is correct
16 Correct 2282 ms 1892 KB Output is correct
17 Correct 473 ms 1956 KB Output is correct
18 Correct 466 ms 1840 KB Output is correct
19 Correct 468 ms 1888 KB Output is correct
20 Correct 496 ms 1848 KB Output is correct
21 Correct 545 ms 1904 KB Output is correct
22 Correct 462 ms 1984 KB Output is correct
23 Correct 698 ms 1856 KB Output is correct
24 Correct 10 ms 1756 KB Output is correct
25 Correct 8 ms 1740 KB Output is correct
26 Correct 11 ms 1808 KB Output is correct
27 Correct 7 ms 1724 KB Output is correct
28 Correct 9 ms 1904 KB Output is correct
29 Correct 24 ms 1964 KB Output is correct
30 Correct 42 ms 1804 KB Output is correct