Submission #1202030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202030		Nelt	Sphinx's Riddle (IOI24_sphinx)	C++20	0 / 100	0 ms	412 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;

#include <bits/stdc++.h>
using namespace std;

vector<int> find_colours(int N,
                         vector<int> X,
                         vector<int> Y)
{
    // (You can omit the DSU‐on‐edges pre‑step if you like —
    //  it doesn’t change the asymptotic experiment count.)

    // Phase 2: bitwise recovery of each C[i]
    int B = 0;
    while ((1 << B) < N)
        ++B; // number of bits needed

    vector<int> recovered(N, 0), E(N);
    // For each bit, determine which vertices have that bit = 1
    for (int b = 0; b < B; ++b)
    {
        // Build E so that:
        //   - if we want to “test” vertex i for bit b = 1, set E[i] = -1
        //     (so vertex i keeps its original colour C[i]),
        //   - otherwise set E[i] = N (the Sphinx’s colour).
        //
        // After recolouring, the Sphinx‐coloured vertices (those with E[i]=N)
        // form exactly one connected component (since the original graph
        // is connected and we gave them all the same colour).  Each vertex
        // for which E[i] = -1 becomes its own singleton component unless
        // its original bit‑b = 1, in which case it merges into the Sphinx
        // component (because then its recoloured colour = Sphinx’s colour
        // for this experiment).
        //
        // Thus the total #components = 1 (the big Sphinx blob of all i with
        // bit‑b=1) + (# of i with bit‑b=0).  We therefore can infer, for
        // each i, whether bit‑b of C[i] = 1 by seeing if flipping E[i]
        // from N to –1 *decreases* the component count by 1.

        // first, set E[i]=N for all i
        fill(E.begin(), E.end(), N);
        int base = perform_experiment(E);
        // base = 1 + (# vertices whose bit‑b = 0)

        // now test each i individually
        for (int i = 0; i < N; ++i)
        {
            // “unmask” i
            E[i] = -1;
            int comps = perform_experiment(E);
            // if C[i] has bit b = 1, then giving it original colour
            // means it joins the big Sphinx blob ⇒ comps = base − 1
            // otherwise it stays its own singleton ⇒ comps = base + 0
            if (comps == base - 1)
            {
                recovered[i] |= (1 << b);
            }
            // restore
            E[i] = N;
        }
    }

    return recovered;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 3
• Subtask 2: 0 / 7
• Subtask 3: 0 / 33
• Subtask 4: 0 / 21
• Subtask 5: 0 / 36