oj.uz

Submission #813121

# Submission time Handle Problem Language Result Execution time Memory
813121 2023-08-07T13:42:20 Z Theo830 Flight to the Ford (BOI22_communication) C++17
74 / 100
 2731 ms 2148 KB 
#include"communication.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int> > >adj;
vector<int>arr;
void encode(int n, int x){
    vector<int>arr;
    set<int>pos;
    for(int j = 0;j < 30;j++){
        pos.insert(j);
        if(x & (1<<j)){
            arr.push_back(1);
        }
        else{
            arr.push_back(0);
        }
    }
    while(pos.size() > 1){
        auto it = pos.begin();
        auto it2 = pos.begin();
        it2++;
        int i = (*it),j = (*it2);
        int a = send(arr[i]);
        int b = send(arr[j]);
        int c = send(arr[j]);
        int d = send(arr[i]);
        if(b == c){
            pos.erase(j);
        }
        else{
            pos.erase(i);
        }
    }
}
void dfs(int idx,int cur){
    arr[idx] = cur;
    for(auto x:adj[idx]){
        dfs(x.first,cur ^ x.second);
    }
}
pair<int, int> decode(int n){
    int A = 0,B = 0;
    adj.assign(35,vector<pair<int,int> >());
    set<int>pos;
    for(int j = 0;j < 30;j++){
        pos.insert(j);
    }
    arr.assign(30,0);
    while(pos.size() > 1){
        auto it = pos.begin();
        auto it2 = pos.begin();
        it2++;
        int i = (*it),j = (*it2);
        int a = receive();
        int b = receive();
        int c = receive();
        int d = receive();
        if(b == c){
            arr[j] = b;
            dfs(j,b);
            pos.erase(j);
        }
        else if(a == d){
            arr[i] = a;
            dfs(i,a);
            pos.erase(i);
        }
        else{
            adj[j].push_back({i,a ^ c});
            pos.erase(i);
        }
    }
    auto it = pos.begin();
    int i = (*it);
    dfs(i,0);
    for(int j = 0;j < 30;j++){
        if(arr[j]){
            A += (1<<j);
        }
    }
    dfs(i,1);
    for(int j = 0;j < 30;j++){
        if(arr[j]){
            B += (1<<j);
        }
    }
    A = max(1,A);
    B = max(1,B);
    B = min(n,B);
    A = min(n,A);
    return {A,B};
}

Compilation message

communication.cpp: In function 'void encode(int, int)':
communication.cpp:23:13: warning: unused variable 'a' [-Wunused-variable]
   23 |         int a = send(arr[i]);
      |             ^
communication.cpp:26:13: warning: unused variable 'd' [-Wunused-variable]
   26 |         int d = send(arr[i]);
      |             ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 1656 KB Output is correct
2 Correct 147 ms 1664 KB Output is correct
3 Correct 127 ms 1684 KB Output is correct
4 Correct 73 ms 1756 KB Output is correct
5 Correct 136 ms 1752 KB Output is correct
6 Correct 257 ms 1828 KB Output is correct
7 Correct 592 ms 1768 KB Output is correct

Subtask #2
59.00003 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 637 ms 1828 KB Output is partially correct
2 Partially correct 336 ms 1708 KB Output is partially correct
3 Partially correct 334 ms 1708 KB Output is partially correct
4 Partially correct 773 ms 1664 KB Output is partially correct
5 Partially correct 593 ms 1792 KB Output is partially correct
6 Partially correct 541 ms 1780 KB Output is partially correct
7 Partially correct 1990 ms 1796 KB Output is partially correct
8 Partially correct 2731 ms 2148 KB Output is partially correct
9 Partially correct 2426 ms 1784 KB Output is partially correct
10 Partially correct 2360 ms 1924 KB Output is partially correct
11 Partially correct 2415 ms 1988 KB Output is partially correct
12 Partially correct 2110 ms 1968 KB Output is partially correct
13 Partially correct 2402 ms 1984 KB Output is partially correct
14 Partially correct 2461 ms 1920 KB Output is partially correct
15 Partially correct 1579 ms 1792 KB Output is partially correct
16 Partially correct 2661 ms 1728 KB Output is partially correct
17 Partially correct 647 ms 1928 KB Output is partially correct
18 Partially correct 673 ms 1728 KB Output is partially correct
19 Partially correct 635 ms 1828 KB Output is partially correct
20 Partially correct 595 ms 1996 KB Output is partially correct
21 Partially correct 892 ms 1788 KB Output is partially correct
22 Partially correct 530 ms 1748 KB Output is partially correct
23 Partially correct 1120 ms 1816 KB Output is partially correct
24 Correct 98 ms 1672 KB Output is correct
25 Correct 98 ms 1704 KB Output is correct
26 Correct 117 ms 1764 KB Output is correct
27 Correct 66 ms 1732 KB Output is correct
28 Correct 98 ms 1728 KB Output is correct
29 Correct 281 ms 1768 KB Output is correct
30 Correct 516 ms 1708 KB Output is correct