oj.uz

Submission #829515

# Submission time Handle Problem Language Result Execution time Memory
829515 2023-08-18T11:51:18 Z QwertyPi Flight to the Ford (BOI22_communication) C++17
74 / 100
 2324 ms 2116 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);
    while(bits.size() >= 2){
        int b1 = bits.back(); bits.pop_back();
        int b2 = bits.back(); bits.pop_back();

        int s1 = send(a[b1]);
        int s2 = send(a[b2]);
        int s3 = send(a[b2]);

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

        int s4 = send(a[b1]);
        bits.push_back(b2);
    }
}

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();
    while(bits.size() >= 2){
        int b1 = bits.back(); bits.pop_back();
        int b2 = bits.back(); bits.pop_back();

        int s1 = receive();
        int s2 = receive();
        int s3 = receive();

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

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

    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]};
}

Compilation message

communication.cpp: In function 'void encode(int, int)':
communication.cpp:26:13: warning: unused variable 's1' [-Wunused-variable]
   26 |         int s1 = send(a[b1]);
      |             ^~
communication.cpp:35:13: warning: unused variable 's4' [-Wunused-variable]
   35 |         int s4 = send(a[b1]);
      |             ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1720 KB Output is correct
2 Correct 13 ms 1712 KB Output is correct
3 Correct 16 ms 1864 KB Output is correct
4 Correct 8 ms 1804 KB Output is correct
5 Correct 9 ms 1724 KB Output is correct
6 Correct 25 ms 1864 KB Output is correct
7 Correct 40 ms 1700 KB Output is correct

Subtask #2
59.00003 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 542 ms 1732 KB Output is partially correct
2 Partially correct 239 ms 1704 KB Output is partially correct
3 Partially correct 252 ms 1720 KB Output is partially correct
4 Partially correct 547 ms 1660 KB Output is partially correct
5 Partially correct 510 ms 1716 KB Output is partially correct
6 Partially correct 434 ms 1712 KB Output is partially correct
7 Partially correct 1736 ms 1804 KB Output is partially correct
8 Partially correct 2227 ms 2116 KB Output is partially correct
9 Partially correct 2206 ms 1864 KB Output is partially correct
10 Partially correct 1988 ms 1988 KB Output is partially correct
11 Partially correct 2072 ms 1796 KB Output is partially correct
12 Partially correct 2005 ms 1928 KB Output is partially correct
13 Partially correct 2188 ms 1816 KB Output is partially correct
14 Partially correct 2066 ms 1968 KB Output is partially correct
15 Partially correct 1144 ms 1752 KB Output is partially correct
16 Partially correct 2324 ms 1816 KB Output is partially correct
17 Partially correct 702 ms 2016 KB Output is partially correct
18 Correct 578 ms 1984 KB Output is correct
19 Partially correct 605 ms 1724 KB Output is partially correct
20 Correct 575 ms 1764 KB Output is correct
21 Correct 622 ms 1840 KB Output is correct
22 Partially correct 513 ms 1724 KB Output is partially correct
23 Partially correct 1010 ms 1752 KB Output is partially correct
24 Correct 7 ms 1844 KB Output is correct
25 Correct 12 ms 1792 KB Output is correct
26 Correct 15 ms 1712 KB Output is correct
27 Correct 10 ms 1776 KB Output is correct
28 Correct 13 ms 1684 KB Output is correct
29 Correct 30 ms 1920 KB Output is correct
30 Correct 69 ms 1700 KB Output is correct