Submission #1236791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236791		fv3	Sphinx's Riddle (IOI24_sphinx)	C++20	36 / 100	38 ms	420 KiB

sphinx

#include "sphinx.h"

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#ifdef LOCAL
#include "/home/fv3/prog/debug/debug.h"
#else
#define debug(...) 42
#endif

vector<int> find_colours(int n, vector<int> u, vector<int> v) {
    const int m = int(u.size());

    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }

    auto Count = [&](const vector<int>& S) {
        int components_cnt = 0;
        std::vector<bool> vis(n, false);
        for (int i = 0; i < n; i++) {
            if (vis[i]) continue;
            components_cnt++;

            std::queue<int> q;
            vis[i] = true;
            q.push(i);
            while (!q.empty()) {
                int cur = q.front();
                q.pop();
                for (int nxt : adj[cur]) {
                    if (!vis[nxt] && S[nxt] == S[cur]) {
                        vis[nxt] = true;
                        q.push(nxt);
                    }
                }
            }
        }
        return components_cnt;
    };

    vector<int> blue(n, 0), b, r;
    for (int i = 0; i < n; i++) {
        bool go_blue = true;
        for (auto node : adj[i]) {
            if (blue[node]) {
                go_blue = false;
            }
        }

        if (go_blue) {
            blue[i] = 1;
            b.push_back(i);
        } else {
            r.push_back(i);
        }
    }

    vector<int> colours(n, -1);

    // Find colour of all blue's
    auto SolveReds = [&](vector<int> &blues) {
        for (int c = 0; c < n; c++) {
            vector<int> col(n, c);
            for (int i : blues) { col[i] = -1; }

            int initial_experiment = perform_experiment(col);
            while (!blues.empty() && Count(col) != initial_experiment) {
                int lo = 0, hi = int(blues.size()) - 1;
                while (lo < hi) {
                    int mid = lo + (hi - lo) / 2;

                    for (int i : blues) { col[i] = n; };
                    for (int i = lo; i <= mid; i++) {
                        col[blues[i]] = -1;
                    }

                    int perf = perform_experiment(col), cnt = Count(col);
                    if (perf == cnt) {
                        lo = mid + 1;
                    } else {
                        hi = mid;
                    }
                }

                col[blues[lo]] = c;
                colours[blues[lo]] = c;
                blues.erase(blues.begin() + lo);
            }
        }
    };

    SolveReds(r);
    SolveReds(b);

    return colours;
}

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