Submission #1190466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190466		gyg	Sphinx's Riddle (IOI24_sphinx)	C++20	3 / 100	43 ms	912 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array 
#define vec vector

int n;

int qry(vec<int> x, int i = -1, int c = -1) {
    for (int j = 0; j <= i; j++) 
        x[j] = c;
    return perform_experiment(x);
}

vec<int> find_colours(int _n, vec<int> _u, vec<int> _v) {
    n = _n;

    vec<int> cl(n, -1);
    for (int c = 0; c < n; c++) {
        vec<int> qr;
        for (int v = 0; v < n; v++)
            qr.push_back((v == 0) ? -1 : c);
        if (qry(qr) == 1) cl[0] = c;
    }

    for (int c = 0; c < n; c++) {
        if (qry(cl, 0, c) == qry(cl, 0, n)) continue;
        vec<int> qr = cl;
        int lst = n + 1;
        for (int i = 0; i < n; i++) {
            int lw = 0, hg = lst - 1;
            if (lw > hg) break;
            while (lw < hg) {
                int md = (lw + hg + 1) / 2;
                if (i == 0) {
                    if (qry(qr, md, n) > qry(qr, md, c)) lw = md;
                    else hg = md - 1;
                } else {
                    if (qry(qr, md, n) == qry(qr, md, c)) lw = md;
                    else hg = md - 1;
                }
            }
            if (i == 0 && qry(qr, lw, n) <= qry(qr, lw, c)) break;
            if (i != 0 && qry(qr, lw, n) != qry(qr, lw, c)) break;
            lst = lw + 1, cl[lst] = c, qr[lst] = n;
        }
    }
    return cl;
}

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