Submission #1111056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111056		Pioneer	Sphinx's Riddle (IOI24_sphinx)	C++17	36 / 100	106 ms	496 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define sz(s) ((int)s.size())
#define all(v) v.begin(),v.end()

const int MAX=255;

struct dsu{
    int f[MAX];

    void init(int n){
        for(int i=0;i<n;i++)f[i]=i;
    }

    int get(int v){
        return (f[v]==v?v:f[v]=get(f[v]));
    }

    void unite(int a,int b){
        a=get(a),b=get(b);
        f[a]=b;
    }
}d,dd;

int n;
vector<int> g[MAX];

bool bar(int mid,int l,int r){
    vector<int> ask(n,-1);
    for(int i=0;i<mid;i++){
        if(d.get(i)<l||d.get(i)>r){
            ask[i]=n;
        }
    }
    for(int i=mid+1;i<n;i++)ask[i]=n;
    dd.init(n);
    for(int i=0;i<n;i++){
        for(auto to:g[i]){
            if(ask[i]==n&&ask[to]==n){
                dd.unite(i,to);
            }
        }
    }
    for(int i=0;i<mid;i++){
        for(auto to:g[i]){
            if(d.get(i)==d.get(to)){
                dd.unite(i,to);
            }
        }
    }
    vector<int> vec;
    for(int i=0;i<n;i++)vec.pb(dd.get(i));
    sort(all(vec));
    vec.erase(unique(all(vec)),vec.end());
    return (sz(vec)!=perform_experiment(ask));
}

vector<int> g1[MAX];
int dep[MAX];
int use[MAX];
vector<int> ver[2];

void dfs(int v){
    use[v]=1;
    ver[dep[v]].pb(v);
    for(auto to:g1[v]){
        if(use[to])continue;
        dep[to]=(dep[v]^1);
        dfs(to);
    }
}

bool BAR(int l,int r,int color){
    vector<int> ask(n,-1);
    for(int i=0;i<n;i++){
        if(dep[d.get(i)]%2==0)ask[i]=color;
        else{
            if(d.get(i)>=l&&d.get(i)<=r){
                ask[i]=-1;
            }
            else{
                ask[i]=n;
            }
        }
    }
    // for(int x:ask)cout<<x<<" ";
    // cout<<"\n";
    dd.init(n);
    for(int i=0;i<n;i++){
        for(auto to:g[i]){
            if(ask[i]==ask[to])dd.unite(i,to);
        }
    }
    vector<int> vec;
    for(int i=0;i<n;i++)vec.pb(dd.get(i));
    sort(all(vec));
    vec.erase(unique(all(vec)),vec.end());
    // cout<<perform_experiment(ask)<<" "<<sz(vec)<<"\n";
    return (perform_experiment(ask)!=sz(vec));
}

vector<int> find_colours(int N,vector<int> X,vector<int> Y){
    n=N;
    for(int i=0;i<sz(X);i++){
        g[X[i]].pb(Y[i]);
        g[Y[i]].pb(X[i]);
    }
    d.init(n);
    for(int i=1;i<N;i++){
        vector<int> v;
        for(auto to:g[i]){
            if(to<i){
                v.pb(d.get(to));
            }
        }
        sort(all(v));
        v.erase(unique(all(v)),v.end());
        int l=0;
        vector<int> mrg;
        while(l<sz(v)&&bar(i,v[l],v.back())){
            int r=sz(v)-2,res=sz(v)-1;
            int L=l;
            while(L<=r){
                int mid=(L+r)/2;
                if(bar(i,v[l],v[mid])){
                    r=mid-1;
                    res=mid;
                }
                else{
                    L=mid+1;
                }
            }
            l=res+1;
            mrg.pb(v[res]);
        }
        for(auto to:mrg){
            d.unite(i,to);
        }
    }
    vector<int> cmp;
    for(int i=0;i<n;i++)cmp.pb(d.get(i));
    sort(all(cmp));
    cmp.erase(unique(all(cmp)),cmp.end());
    for(int i=0;i<n;i++){
        for(auto to:g[i]){
            if(d.get(i)!=d.get(to)){
                g1[d.get(i)].pb(d.get(to));
                g1[d.get(to)].pb(d.get(i));
            }
        }
    }
    for(int i=0;i<n;i++){
        sort(all(g1[i]));
        g1[i].erase(unique(all(g1[i])),g1[i].end());
    }
    vector<int> ans(n,-1);
    dfs(cmp[0]);
    if(ver[0].empty()||ver[1].empty()){
        if(ver[0].empty())swap(ver[0],ver[1]);
        for(int i=0;i<n;i++){
            vector<int> ask(n,-1);
            ask[0]=i;
            // cout<<perform_experiment(ask)<<"\n";
            if(perform_experiment(ask)==1)return vector<int>(n,i);
        }
    }
    for(int i=0;i<n;i++){
        int l=0;
        vector<int> vertex;
        while(l<sz(ver[1])&&BAR(ver[1][l],ver[1][sz(ver[1])-1],i)){
            int r=sz(ver[1])-2,res=sz(ver[1])-1;
            int L=l;
            while(L<=r){
                int mid=(L+r)/2;
                if(BAR(ver[1][l],ver[1][mid],i)){
                    r=mid-1;
                    res=mid;
                }
                else L=mid+1;
            }
            vertex.pb(ver[1][res]);
            l=res+1;
        }
        for(auto v:vertex){
            for(int j=0;j<n;j++){
                if(d.get(j)==v)ans[j]=i;
            }
        }
    }
    swap(ver[0],ver[1]);
    for(int i=0;i<n;i++)dep[i]^=1;
    for(int i=0;i<n;i++){
        int l=0;
        vector<int> vertex;
        // if(i==0)cout<<BAR(ver[1][l],ver[1][sz(ver[1])-1],i)<<"\n";
        while(l<sz(ver[1])&&BAR(ver[1][l],ver[1][sz(ver[1])-1],i)){
            int r=sz(ver[1])-2,res=sz(ver[1])-1;
            int L=l;
            while(L<=r){
                int mid=(L+r)/2;
                if(BAR(ver[1][l],ver[1][mid],i)){
                    r=mid-1;
                    res=mid;
                }
                else L=mid+1;
            }
            vertex.pb(ver[1][res]);
            l=res+1;
        }
        for(auto v:vertex){
            for(int j=0;j<n;j++){
                if(d.get(j)==v)ans[j]=i;
            }
        }
    }
    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