Submission #1240807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240807		fv3	Sphinx's Riddle (IOI24_sphinx)	C++20	100 / 100	69 ms	1208 KiB

sphinx

#include "sphinx.h"

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

using ll = long long;
#define all(x) x.begin(), x.end()

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;
        vector<bool> vis(n, false);
        for (int i = 0; i < n; i++) {
            if (vis[i]) continue;
            components_cnt++;

            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), blues;
    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;
            blues.push_back(i);
        }
    }

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

    // Find colour of all blue's
    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;
                }

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

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

    vector<int> id;
    for (int i = 0; i < n; i++) {
        if (!blue[i]) {
            id.push_back(i);
        }
    }

    mt19937 mt(time(0));
    shuffle(all(id), mt);

    set<int> relevant_colours;
    int neutral;
    {
        vector<int> col(n, -1);
        for (int i = 0; i < n; i++) if (blue[i]) {
            col[i] = n;
        }
        int exp = perform_experiment(col);

        for (int c = 0; c < n; c++) {
            for (int i = 0; i < n; i++) if (blue[i]) {
                col[i] = c;
            }
            if (perform_experiment(col) != exp) {
                relevant_colours.insert(c);
            }
        }

        for (int c = 0; c < n; c++) {
            if (relevant_colours.count(c)) continue;
            neutral = c;
            break;
        }
    }
    
    map<pair<int, int>, set<int>> ranges;
    auto Solve = [&](auto&& self, int lo, int hi, const set<int>& s) -> void {
        assert(hi - lo + 1 >= int(s.size()));

        if (hi == lo) {
            colours[id[lo]] = *s.begin();
            return;
        }

        int mid = lo + (hi - lo) / 2;

        if (s.size() == 1) {
            self(self, lo, mid, s);
            self(self, mid+1, hi, s);
            return;
        }

        set<int> l, r;

        auto Col = [&](int c, int tl, int tr) -> vector<int> {
            vector<int> col(n, n);
            for (int i = 0; i < n; i++) if (blue[i]) {
                col[i] = c;
            }
            for (int i = tl; i <= tr; i++) {
                col[id[i]] = -1;
            }
            return col;
        };

        int exp_l = -1, exp_r = -1;

        for (int c : s) {
            if (int(l.size()) == mid - lo + 1) {
                r.insert(c);
                continue;
            }
            vector<int> col = Col(c, lo, mid);
            if (exp_l == -1) {
                exp_l = lo == mid ? Count(Col(neutral, lo, mid)) : perform_experiment(Col(neutral, lo, mid));
            }
            if (perform_experiment(col) == exp_l) {
                r.insert(c);
            } else {
                l.insert(c);
            }
        }

        for (int c : s) {
            if (int(r.size()) == hi - mid) break;
            if (r.count(c)) continue;

            if (exp_r == -1) {
                exp_r = mid+1 == hi ? Count(Col(neutral, mid+1, hi)) : perform_experiment(Col(neutral, mid+1, hi));
            }
            if (perform_experiment(Col(c, mid+1, hi)) != exp_r) {
                r.insert(c);
            }
        }

        self(self, lo, mid, l);
        self(self, mid+1, hi, r);
    };

    Solve(Solve, 0, int(id.size())-1, relevant_colours);
    return colours;
}

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