oj.uz

Submission #813109

# Submission time Handle Problem Language Result Execution time Memory
813109 2023-08-07T13:35:46 Z Theo830 Flight to the Ford (BOI22_communication) C++17
15 / 100
 31 ms 1832 KB 
#include"communication.h"
#include <bits/stdc++.h>
using namespace std;
const int bits = 2;
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 < bits;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(bits+5,vector<pair<int,int> >());
    set<int>pos;
    for(int j = 0;j < bits;j++){
        pos.insert(j);
    }
    arr.assign(bits,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;
            pos.erase(j);
        }
        else if(a == d){
            arr[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 < bits;j++){
        if(arr[j]){
            A += (1<<j);
        }
    }
    dfs(i,1);
    for(int j = 0;j < bits;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:24:13: warning: unused variable 'a' [-Wunused-variable]
   24 |         int a = send(arr[i]);
      |             ^
communication.cpp:27:13: warning: unused variable 'd' [-Wunused-variable]
   27 |         int d = send(arr[i]);
      |             ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1784 KB Output is correct
2 Correct 8 ms 1720 KB Output is correct
3 Correct 14 ms 1832 KB Output is correct
4 Correct 7 ms 1664 KB Output is correct
5 Correct 7 ms 1748 KB Output is correct
6 Correct 17 ms 1788 KB Output is correct
7 Correct 31 ms 1700 KB Output is correct

Subtask #2
0.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 200 KB Not correct
2 Halted 0 ms 0 KB -