Submission #1187277

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

Alice

#include "Alice.h"
#include <vector>
#include <utility>
using namespace std;

// Alice chooses n and encodes X in leaf‐edges:
//  - central edge: (1,2)
//  - for each bit j∈[0,3], R=3 leaves u=3+j*R…3+j*R+2:
//      connect to 1 if bit j of X is 0, else to 2
vector<pair<int,int>> Alice() {
    const int B = 4, R = 3;
    int n = B*R + 2; 
    long long X = setN(n);  // returns the secret X∈[1..10]&#8203;:contentReference[oaicite:1]{index=1}
    vector<pair<int,int>> edges;
    // central spine
    edges.emplace_back(1,2);
    // leaf equations
    for (int j = 0; j < B; j++) {
        int bit = (X >> j) & 1;
        for (int r = 0; r < R; r++) {
            int u = 3 + j*R + r;
            edges.emplace_back(bit==0 ? 1 : 2, u);
        }
    }
    return edges;
}

Bob

#include "Bob.h"
#include <vector>
#include <utility>
using namespace std;

// Bob receives the remaining m edges (sorted), deletes the central
// (1,2) if present, then for each bit j scans its 3 leaves to recover
// at least one surviving edge and hence that bit.
long long Bob(vector<pair<int,int>> V) {
    // collect edges in a set for quick lookup
    // skip center (1,2)
    vector<bool> present(15, false);
    for (auto &e : V) {
        int u = e.first, v = e.second;
        if (u > v) swap(u,v);
        if (u==1 && v==2) continue;  // ignore central&#8203;:contentReference[oaicite:4]{index=4}
        present[v] = (u==1 ? false : true);
    }
    long long X = 0;
    const int B = 4, R = 3;
    for (int j = 0; j < B; j++) {
        // scan the 3 leaves for bit j
        int bit = 0;
        for (int r = 0; r < R; r++) {
            int u = 3 + j*R + r;
            if (!present[u]) { bit = 0; break; }
            else { bit = 1; break; }
        }
        X |= ((long long)(bit) << j);
    }
    return X;
}

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