Submission #1148614

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148614		Ludissey	Sphinx's Riddle (IOI24_sphinx)	C++20	36 / 100	35 ms	428 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
using namespace std;

#define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

ordered_set os; 


int leftCOLOR=0;
int rightCOLOR=0;
int kcol=0;
int n;
vector<int> E;
vector<int> G;
queue<int> torem;

int eval(int l, int r, int val){
    return (r-l+1)-(val-1)/2;
}

void dc(int l, int r, int val){
    if(val==0) return;
    if(l==r){
        int x=*os.find_by_order(l);
        G[x]=kcol;
        torem.push(x);
        return;
    }
    int mid=(l+r)/2;
    for (int i = 0; i < n; i++){
        if(os.find(i)!=os.end()&&(int)os.order_of_key(i)>=l&&(int)os.order_of_key(i)<=mid) E[i]=-1;
        else E[i]=kcol;
    }
    int exp=eval(l,mid,perform_experiment(E));
    dc(l,mid,exp);
    dc(mid+1,r,val-exp);
}



vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
    n=N;
    //determine left color
    E.resize(N,N);
    G.resize(N,N);
    E[0]=-1;
    E[1]=leftCOLOR;  
    int pf=perform_experiment(E);
    while((pf==3&&N>2)||(pf==2&&N==2)){
        leftCOLOR++;
        E[1]=leftCOLOR;
        pf=perform_experiment(E);
    }
    G[0]=leftCOLOR;
    //determine right color
    for (int i = 0; i < n; i++) E[i]=N;
    E[N-1]=-1;
    E[N-2]=rightCOLOR;  
    pf=perform_experiment(E);
    while((pf==3&&N>2)||(pf==2&&N==2)){
        rightCOLOR++;
        E[N-2]=rightCOLOR;
        pf=perform_experiment(E);
    }
    G[N-1]=rightCOLOR;

    for (int i = 1; i < n-1; i++)
    {
        if(i%2==0) os.insert(i);
    }
  
    // les truc pair
    while(kcol<n)
    {
        for (int i = 0; i < n; i++)
        {
            if(os.find(i)!=os.end()) E[i]=-1;
            else E[i]=kcol;
        }
        int val=perform_experiment(E);
        if(os.empty()) break;
        dc(0,sz(os)-1,eval(0,sz(os)-1,val));
        while(!torem.empty()){
            int u=torem.front(); torem.pop();
            os.erase(os.find_by_order(os.order_of_key(u)));
        }
        kcol++;
    }
    kcol=0;
    for (int i = 1; i < n-1; i++)
    {
        if(i%2) os.insert(i);
    }
    while(kcol<n)
    {
        for (int i = 0; i < n; i++)
        {
            if(os.find(i)!=os.end()) E[i]=-1;
            else E[i]=kcol;
        }
        int val=perform_experiment(E);
        if(os.empty()) break;
        dc(0,sz(os)-1,eval(0,sz(os)-1,val));
        while(!torem.empty()){
            int u=torem.front(); torem.pop();
            os.erase(os.find_by_order(os.order_of_key(u)));
        }
        kcol++;
    }
    kcol=0;
    return G;
}

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