제출 #1190468

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190468		gyg	스핑크스 (IOI24_sphinx)	C++20	3 / 100	42 ms	924 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;
    }

    map<int, int> str;
    for (int i = 0; i < n; i++) str[i] = qry(cl, i, n);

    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 (str[md] > 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 && str[lw] <= 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