Submission #1194700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194700		TahirAliyev	Sphinx's Riddle (IOI24_sphinx)	C++20	36 / 100	38 ms	440 KiB

sphinx

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

int n;
vector<int> ans;

bool aske(int l, int r, int x){
    vector<int> v(n);
    for(int i = 0; i < n; i++){
        if(i & 1) v[i] = x;
        else v[i] = n;
    }
    for(int i = l; i <= r; i++){
        if(!(i & 1)) v[i] = -1;
    }
    if(perform_experiment(v) != n) return 1;
    return 0;
}
bool asko(int l, int r, int x){
    vector<int> v(n);
    for(int i = 0; i < n; i++){
        if(i & 1) v[i] = n;
        else v[i] = x;
    }
    for(int i = l; i <= r; i++){
        if(i & 1) v[i] = -1;
    }
    if(perform_experiment(v) != n) return 1;
    return 0;
}

vector<int> find_colours(int N, vector<int> X, vector<int> Y){
    n = N;
    ans.resize(n);
    for(int x = 0; x < n; x++){
        int l = 0, r = n - 1;
        while(asko(l, r, x)){
            while(l < r){
                int mid = (l + r) / 2;
                if(asko(l, mid, x)) r = mid;
                else l = mid + 1;
            }
            ans[l] = x;
            l++;
            r = n - 1;
        }
        l = 0, r = n - 1;
        while(aske(l, r, x)){
            while(l < r){
                int mid = (l + r) / 2;
                if(aske(l, mid, x)) r = mid;
                else l = mid + 1;
            }
            ans[l] = x;
            l++;
            r = n - 1;
        }
    }
    return ans;
}

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