oj.uz

Submission #829529

# Submission time Handle Problem Language Result Execution time Memory
829529 2023-08-18T12:04:52 Z QwertyPi Flight to the Ford (BOI22_communication) C++17
90 / 100
 2154 ms 1976 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;
    vector<int> bits; for(int j = 0; j < B; j++) bits.push_back(j);
    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;
    vector<int> bits; for(int j = 0; j < B; j++) bits.push_back(j);
    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 6 ms 1636 KB Output is correct
2 Correct 9 ms 1732 KB Output is correct
3 Correct 9 ms 1716 KB Output is correct
4 Correct 8 ms 1724 KB Output is correct
5 Correct 8 ms 1716 KB Output is correct
6 Correct 24 ms 1896 KB Output is correct
7 Correct 36 ms 1764 KB Output is correct

Subtask #2
75.000005 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 413 ms 1664 KB Output is partially correct
2 Partially correct 195 ms 1680 KB Output is partially correct
3 Partially correct 261 ms 1724 KB Output is partially correct
4 Partially correct 629 ms 1684 KB Output is partially correct
5 Partially correct 398 ms 1692 KB Output is partially correct
6 Correct 455 ms 1680 KB Output is correct
7 Correct 1216 ms 1808 KB Output is correct
8 Correct 2144 ms 1892 KB Output is correct
9 Correct 1750 ms 1796 KB Output is correct
10 Correct 1991 ms 1976 KB Output is correct
11 Correct 1784 ms 1840 KB Output is correct
12 Correct 1984 ms 1928 KB Output is correct
13 Correct 1875 ms 1896 KB Output is correct
14 Correct 1837 ms 1876 KB Output is correct
15 Correct 1020 ms 1760 KB Output is correct
16 Correct 2154 ms 1728 KB Output is correct
17 Correct 542 ms 1800 KB Output is correct
18 Correct 546 ms 1784 KB Output is correct
19 Correct 596 ms 1780 KB Output is correct
20 Correct 504 ms 1792 KB Output is correct
21 Correct 549 ms 1784 KB Output is correct
22 Correct 522 ms 1852 KB Output is correct
23 Correct 865 ms 1820 KB Output is correct
24 Correct 10 ms 1708 KB Output is correct
25 Correct 12 ms 1716 KB Output is correct
26 Correct 11 ms 1660 KB Output is correct
27 Correct 9 ms 1740 KB Output is correct
28 Correct 13 ms 1744 KB Output is correct
29 Correct 27 ms 1860 KB Output is correct
30 Correct 61 ms 1664 KB Output is correct