Submission #1202116

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

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
struct Dsu
{
    ll n, ans;
    vector<ll> dsu;
    Dsu(ll sz = 1)
    {
        n = sz;
        ans = n;
        dsu.resize(n + 1, -1);
        init();
    }
    void init()
    {
        for (ll i = 1; i <= n; i++)
            dsu[i] = -1;
    }
    bool Union(ll x, ll y)
    {
        x = repr(x), y = repr(y);
        if (x == y)
            return false;
        if (dsu[x] < dsu[y])
            swap(x, y);
        ans--;
        dsu[y] += dsu[x];
        dsu[x] = y;
        return true;
    }
    ll repr(ll x)
    {
        if (dsu[x] < 0)
            return x;
        return dsu[x] = repr(dsu[x]);
    }
    ll query()
    {
        return ans;
    }
    ll size(ll x)
    {
        return -dsu[repr(x)];
    }
};
const ll N = 255;
bool g[N][N];

ll n;

vector<int> find_colours(int N, vector<int> X, vector<int> Y)
{
    n = N;
    for (ll i = 0; i < X.size(); i++)
        g[X[i]][Y[i]] = g[Y[i]][X[i]] = 1;
    vector<int> ans(n);
    vector<int> send(n);
    for (ll i = 0; i < n; i++)
    {
        send.assign(n, i);
        send[n - 1] = -1;
        if (perform_experiment(send) == 1) ans[n - 1] = i;
    }
    for (ll col = 0; col < n; col++)
    {
        for (ll ptr = 0; ptr < n - 1;)
        {
            ll l = ptr, r = n - 2, last = n - 1;
            while (l <= r)
            {
                ll mid = (l + r) >> 1;
                send.assign(n, col);
                for (ll i = 0; i <= mid; i++) send[i] = -1;
                if (perform_experiment(send) <= mid) r = mid - 1, last = mid;
                else l = mid + 1;
            }
            if (last != n - 1) ans[last] = col;
            ptr = last + 1;
        }
    }
    return ans;
}

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