Submission #1192230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192230		NotLinux	Sphinx's Riddle (IOI24_sphinx)	C++20	36 / 100	41 ms	964 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
vector<int> find_colours(int n, vector<int> x, vector<int> y) {
    vector<int>col(n);
    if(n <= 0){
        for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
                vector<int>vec(n,j);
                vec[i] = -1;
                if(perform_experiment(vec) == 1){
                    col[i] = j;
                    break;
                }
            }
        }
    }
    else if(sz(x) == n * (n-1) / 2){
        // ilkinin rengini bul
        for(int j = 0;j<n;j++){
            vector<int>vec(n,j);
            vec[0] = -1;
            if(perform_experiment(vec) == 1){
                col[0] = j;
                break;
            }
        }
        map<pair<int,int>,int>mpa;
        auto getran = [&](int l , int r , int renk){// bu rangede bu renkten varmi
            vector<int>vec(n,n);
            for(int i = l;i<=r;i++)vec[i] = -1;
            int res1;
            if(mpa.count({l,r}))res1 = mpa[{l,r}];
            else{
                res1 = perform_experiment(vec);
                mpa[{l,r}] = res1;
            }
            for(int i = 0;i<n;i++){
                if(vec[i] == n)vec[i] = renk;
            }
            int res2 = perform_experiment(vec);
            // cout << "res1 : " << res1 << " , res2 : " << res2 << endl;
            // cout << "getran : " << l << " " << r << " " << renk << " : " << (res2 < res1) << endl;
            return res2 < res1;
        };
        // cout << "flag0" << endl;
        for(int i = 0;i<n;i++){
            int lst = 1;
            while(lst < n and getran(lst,n-1,i)){
                int l = lst , r = n-1;
                while(l < r){
                    int mid = (l + r) / 2;
                    if(getran(l,mid,i))r = mid;
                    else l = mid+1;
                }
                col[l] = i;
                lst = l+1;
            }
        }
    }
    else{
        // ilkinin rengini bul
        for(int j = 0;j<n;j++){
            vector<int>vec(n,j);
            vec[0] = -1;
            if(perform_experiment(vec) == 1){
                col[0] = j;
                break;
            }
        }
        // sonuncunun rengini bul
        for(int j = 0;j<n;j++){
            vector<int>vec(n,j);
            vec[n-1] = -1;
            if(perform_experiment(vec) == 1){
                col[n-1] = j;
                break;
            }
        }
        map<array<int,4>,int>mpa;
        auto getran = [&](int l , int r , int renk , int odd){// l r araliginda tek/ciftlerde kac tane renk var
            if(l == r and (l&1) != (odd&1))return 0;
            else if(mpa.count({l,r,renk,odd}))return mpa[{l,r,renk,odd}];
            vector<int>vec(n,renk);
            int saymaca = 0;
            for(int i = l;i<=r;i++){
                if((i&1) == (odd&1)){
                    vec[i] = -1;
                    saymaca++;
                }
            }
            int ret = saymaca - (perform_experiment(vec) - 1) / 2;
            mpa[{l,r,renk,odd}] = ret;
            return ret;
        };
        for(int i = 0;i<2;i++){
            for(int j = 0;j<n;j++){
                int sayac = 0 , lst = 0;
                while(sayac < getran(1,n-2,j,i)){
                    int l = lst+1 , r = n-2;
                    while(l < r){
                        int mid = (l + r) / 2;
                        if(getran(l,mid,j,i))r = mid;
                        else l = mid+1;
                    }
                    col[l] = j;
                    sayac++;
                    lst = l;
                }
            }
        }
    }
    return col;
}

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