Submission #723153

#	Time	Username	Problem	Language	Result	Execution time	Memory
723153		sunnat	Flight to the Ford (BOI22_communication)	C++17	0 / 100	167 ms	1652 KiB

communication

#include"communication.h"
#include <vector>
#include <algorithm>
#include <random>
#include <iostream>

using namespace std;
random_device rnd;
//
// --- 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.:
//     
// 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) {
    while(N > 0){
        N /= 2;
        send(x%2);
        send(x%2);
        send(x%2);
        x /= 2;        
    }
}
vector<int> a, res;
void brute_force(int x, int i, bool f){
    if(i*3 == a.size()){
        res.push_back(x);
        return;
    }
    int j = i*3;
    if(f){
        if(a[j] != a[j+1] && a[j] != a[j+2])
            return;
        brute_force(x|(a[j]<<i), i+1, a[j] != a[j+2]);
        return;
    }
    
    if(a[j] == a[j+1])
        brute_force(x|(a[j]<<i), i+1, a[j] != a[j+2]);
    else if(a[j+1] == a[j+2])
        brute_force(x|(a[j+1]<<i), i+1, false);
    else{
        brute_force(x|(a[j]<<i), i+1, a[j] != a[j+2]);
        brute_force(x|(a[j+1]<<i), i+1, a[j+1] != a[j+2]);
    }
}
std::pair<int, int> decode(int N) {
    a.clear();
    while(N > 0){
        N /= 2;
        a.push_back(receive());
        a.push_back(receive());
        a.push_back(receive());
    }
    res.clear();
    brute_force(0, 0, 0);
    sort(res.begin(), res.end());
    
    if(res[0] == 0) res.erase(res.begin());
    if(res.size() == 1) return {res[0], res[0]};
    int i = rnd() % res.size(), j;
    while((j = rnd() % res.size()) == i);
    // cout << res[i] << ' ' << res[j] << endl;
    return {res[0], res[1]};
}

Compilation message (stderr)

communication.cpp: In function 'void brute_force(int, int, bool)':
communication.cpp:32:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     if(i*3 == a.size()){
      |        ~~~~^~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85