Submission #1129627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129627		c0det1ger	Sphinx's Riddle (IOI24_sphinx)	C++20	64 / 100	53 ms	656 KiB

sphinx

#include <bits/stdc++.h>
using namespace std;
 
//#define int long long
#define double long double

int perform_experiment(vector<int> E);

vector<int> find_colours(int N, vector<int> X, vector<int> Y){
    if (N <= 50){
        vector<int> c(N);
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                vector<int> e(N);
                for (int k = 0; k < N; k++){
                    if (k == i){
                        e[k] = -1;
                    }
                    else{
                        e[k] = j;
                    }
                }
                int ans = perform_experiment(e);
                if (ans == 1){
                    c[i] = j;
                    break;
                }
            }
        }
        return c;
    }
    else if (X.size() == N - 1){
        vector<int> c(N);
        vector<int> done(N);
        
        int cnt = 0;
        for (int i = 0; i < N; i++){
            if (i % 2 == 1){
                cnt++;
            }
        }
        
        int cur = 0;
        while (cnt > 0){
            vector<int> e(N);
            for (int i = 0; i < N; i++){
                if (i % 2 == 0){
                    e[i] = cur;
                }
                else if (done[i]){
                    e[i] = (cur + 1) % N;
                }
                else{
                    e[i] = -1;
                }
            }
            int res = perform_experiment(e);
            if (res == N){
                cur++;
                continue;
            }
            int l = 0, r = N - 1;
            while (l < r){
                int mid = (l + r) / 2;
                vector<int> e(N, N);
                for (int i = l; i <= mid; i++){
                    if (i % 2 == 0){
                        e[i] = cur;
                    }
                    else if (done[i]){
                        e[i] = (cur + 1) % N;
                    }
                    else{
                        e[i] = -1;
                    }
                }
                int res = perform_experiment(e);
                if ((mid - l + 1 != 1 || (mid - l + 1 == 1 && l % 2 == 0)) && res == ((l > 0) + (mid < N - 1) + (mid - l + 1))){
                    l = mid + 1;
                }
                else{
                    r = mid;
                }
            }
            done[l] = 1;
            c[l] = cur;
            cnt--;
        }
        
        cnt = (N + 1) / 2;
        cur = 0;
        
        while (cnt > 0){
            vector<int> e(N);
            for (int i = 0; i < N; i++){
                if (i % 2 == 1){
                    e[i] = cur;
                }
                else if (done[i]){
                    e[i] = (cur + 1) % N;
                }
                else{
                    e[i] = -1;
                }
            }
            int res = perform_experiment(e);
            if (res == N){
                cur++;
                continue;
            }
            int l = 0, r = N - 1;
            while (l < r){
                int mid = (l + r) / 2;
                vector<int> e(N, N);
                for (int i = l; i <= mid; i++){
                    if (i % 2 == 1){
                        e[i] = cur;
                    }
                    else if (done[i]){
                        e[i] = (cur + 1) % N;
                    }
                    else{
                        e[i] = -1;
                    }
                }
                int res = perform_experiment(e);
                if ((mid - l + 1 != 1 || (mid - l + 1 == 1 && l % 2 == 1)) && res == ((l > 0) + (mid < N - 1) + (mid - l + 1))){
                    l = mid + 1;
                }
                else{
                    r = mid;
                }
            }
            done[l] = 1;
            c[l] = cur;
            cnt--;
        }
        
        return c;
    }
    else{
        
        vector<int> c(N);
        
        for (int i = 0; i < N; i++){
            int l = 0, r = N - 1;
            while (l < r){
                int mid = (l + r) / 2;
                vector<int> e(N);
                int cur = l;
                for (int j = 0; j < N; j++){
                    if (j == i){
                        e[j] = -1;
                    }
                    else if (cur > mid){
                        e[j] = N;
                    }
                    else{
                        e[j] = cur;
                        cur++;
                    }
                }
                int res = perform_experiment(e);
                if (res == (mid - l + 1) + 1 + min(1, N - 2)){
                    l = mid + 1;
                }
                else{
                    r = mid;
                }
            }
            c[i] = l;
        }
        
        return c;
    }
}

/*
 ____   ___    ___     ____  _____          ____    ____   ___
|      |   |  |   \   |        |     /|    |       |      |   \
|      |   |  |    |  |____    |      |    |   _   |____  |___/
|      |   |  |    |  |        |      |    |    |  |      |  \
|____  |___|  |___/   |____    |    __|__  |____|  |____  |   \
 
*/

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