Submission #1243311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243311		SpyrosAliv	Sphinx's Riddle (IOI24_sphinx)	C++20	24 / 100	45 ms	1168 KiB

sphinx

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

int n, m;
vector<vector<int>> g;

vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
    n = N;
    m = Y.size();
    g.resize(n);
    for (int i = 0; i < m; i++) {
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    vector<int> fin(n, -1);
    for (int i = 0; i < n; i++) {
        int lo = 0, hi = n-2;
        int ans = n-1;
        while (lo <= hi) {
            vector<int> willAsk(n);
            int mid = (lo + hi) / 2;
            int curr = 0;
            set<int> comps;
            for (int j = 0; j < n; j++) {
                if (j == i) willAsk[j] = -1;
                else {
                    willAsk[j] = curr++;
                }
                if (curr > mid) curr = n;
                comps.insert(willAsk[j]);
            }
            int tot = perform_experiment(willAsk);
            if (tot != (int)comps.size()) {
                ans = mid;
                hi = mid-1;
            }
            else lo = mid+1;
        }
        fin[i] = ans;
    }
    return fin;
}

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