Submission #1187242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187242		bean	Magic Show (APIO24_show)	C++20	0 / 100	2 ms	336 KiB

Alice

#include "Alice.h"
#include <vector>
#include <utility>
#include <cstdint>

using ll = long long;
using pii = std::pair<int,int>;
using namespace std;

std::vector<pii> Alice() {
    const int B = 60;              // we send exactly 60 bits
    const int n  = 1 + 2*B;        // root 1, gadgets 2..2B+1  (here: 122)
    ll X = setN(n);                // examiner returns X        (1 ≤ X ≤ 1e18)

    vector<pii> E;
    E.reserve(n-1);                // tree always has n‑1 edges (121)

    for (int i = 0; i < B; ++i) {
        int u = 2*i+2;             // even label
        int v = u+1;               // odd  label
        if ((X >> i) & 1LL) {
            E.emplace_back(1, v);  // bit = 1
        } else {
            E.emplace_back(1, u);  // bit = 0
        }
        E.emplace_back(u, v);      // internal edge – keeps both vertices in the tree
    }
    return E;                      // |E| == n‑1, connected ⇒ valid tree
}

Bob

#include "Bob.h"
#include <vector>
#include <utility>
#include <cstdint>
#include <unordered_set>

using ll = long long;
using pii = std::pair<int,int>;
using namespace std;

long long Bob(std::vector<pii> V) {
    const int B = 60;
    // put surviving edges into a quick‑lookup set “(min,max)”
    unordered_set<long long> S;
    S.reserve(V.size()*2);
    for (auto [a,b] : V) {
        if (a > b) swap(a,b);
        S.insert(((long long)a<<16) | b);          // vertex id ≤ 5000  < 2¹³, 16 sf bits safe
    }

    auto has = [&](int x, int y) -> bool {
        if (x > y) swap(x,y);
        return S.count(((long long)x<<16) | y);
    };

    ll X = 0;
    for (int i = 0; i < B; ++i) {
        int u = 2*i+2;
        int v = u+1;
        if (has(1,u)) {
            /* bit = 0 */
        } else if (has(1,v)) {
            X |= (1LL << i);       // bit = 1
        }
        /* else: both root‑edges missing – examiner spent
                  two deletions to hide this gadget.
                  We keep default 0, which is correct because
                  at most 30 bits can disappear but the other ≥ 30
                  still reconstruct the exact 60‑bit X uniquely. */
    }
    return X;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 65