Submission #1099949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099949		ttamx	Sphinx's Riddle (IOI24_sphinx)	C++17	100 / 100	1030 ms	2640 KiB

sphinx

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

using namespace std;

vector<int> find_colours(int n,vector<int> X,vector<int> Y){
    int m=X.size();
    vector<int> ans(n,-1);
    auto count_col=[&](vector<int> a,int col){
        vector<int> pa(n);
        iota(pa.begin(),pa.end(),0);
        function<int(int)> fp=[&](int u){
            return pa[u]=(u==pa[u]?u:fp(pa[u]));
        };
        auto uni=[&](int u,int v){
            u=fp(u),v=fp(v);
            if(u!=v){
                pa[v]=u;
            }
        };
        for(int i=0;i<m;i++){
            if(a[X[i]]==col&&a[Y[i]]==col){
                uni(X[i],Y[i]);
            }
        }
        int res=0;
        for(int i=0;i<n;i++){
            if(a[i]==col&&fp(i)==i){
                res++;
            }
        }
        return res;
    };
    auto query=[&](vector<int> a,int col){
        int res=perform_experiment(a)-count_col(a,col);
        if(col!=n){
            res-=count_col(a,n);
        }
        return res;
    };
    int comp_cnt=0;
    vector<int> pa(n);
    iota(pa.begin(),pa.end(),0);
    function<int(int)> fp=[&](int u){
        return pa[u]=(u==pa[u]?u:fp(pa[u]));
    };
    auto uni=[&](int u,int v){
        u=fp(u),v=fp(v);
        if(u!=v){
            pa[v]=u;
            comp_cnt--;
        }
    };
    vector<int> filter(n,n);
    for(int u=0;u<n;u++){
        comp_cnt++;
        filter[u]=-1;
        int res=query(filter,n);
        int k=comp_cnt-res;
        vector<int> same,cand;
        for(int i=0;i<u;i++){
            if(fp(i)==i){
                cand.emplace_back(i);
            }
        }
        for(int i=0,p=0;i<k;i++){
            int l=p,r=cand.size()-1;
            while(l<r){
                int m=(l+r)/2;
                vector<int> tmp(n,n);
                int cnt=0;
                for(int j=0;j<u;j++){
                    if(cand[p]<=fp(j)&&fp(j)<=cand[m]){
                        if(fp(j)==j){
                            cnt++;
                        }
                    }else{
                        tmp[j]=-1;
                    }
                }
                tmp[u]=-1;
                if(query(tmp,n)!=res-cnt){
                    r=m;
                }else{
                    l=m+1;
                }
            }
            same.emplace_back(cand[l]);
            p=l+1;
        }
        for(auto x:same){
            uni(u,x);
        }
    }
    set<pair<int,int>> edge;
    for(int i=0;i<m;i++){
        int u=fp(X[i]),v=fp(Y[i]);
        if(u>v){
            swap(u,v);
        }
        if(u!=v){
            edge.emplace(u,v);
        }
    }
    vector<vector<int>> adj(n);
    for(auto [u,v]:edge){
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    vector<vector<int>> comp(n);
    for(int i=0;i<n;i++){
        comp[fp(i)].emplace_back(i);
    }
    vector<bool> vis(n);
    vector<vector<int>> node(2);
    int node_cnt=0;
    function<void(int,int)> dfs=[&](int u,int c){
        node_cnt++;
        vis[u]=true;
        node[c].emplace_back(u);
        for(auto v:adj[u]){
            if(!vis[v]){
                dfs(v,c^1);
            }
        }
    };
    for(auto &x:node){
        sort(x.begin(),x.end());
    }
    dfs(fp(0),0);
    auto paint=[&](vector<int> &a,int i,int col){
        for(auto x:comp[i]){
            a[x]=col;
        }
    };
    if(node_cnt==1){
        for(int i=0;i<n;i++){
            vector<int> tmp(n,i);
            tmp[0]=-1;
            if(perform_experiment(tmp)==1){
                return vector<int>(n,i);
            }
        }
        assert(false);
    }
    vector<vector<int>> pos(2);
    for(int i=0;i<2;i++){
        int k=node[i].size();
        pos[i].resize(k);
        iota(pos[i].begin(),pos[i].end(),0);
    }
    for(int col=0;col<n;col++){
        for(int t=0;t<2;t++){
            vector<int> filter(n,col);
            for(auto i:node[t]){
                paint(filter,i,-1);
            }
            vector<int> found;
            for(int i=0;i<pos[t].size();i++){
                for(int j=0;j<pos[t][i];j++){
                    paint(filter,node[t][j],n);
                }
                if(query(filter,col)==node[t].size()-pos[t][i]){
                    break;
                }
                int l=i,r=pos[t].size()-1;
                while(l<r){
                    int m=(l+r)/2;
                    vector<int> tmp(n,col);
                    for(int j=0;j<node[t].size();j++){
                        if(j<pos[t][i]||pos[t][m]<j){
                            paint(tmp,node[t][j],n);
                        }else{
                            paint(tmp,node[t][j],-1);
                        }
                    }
                    if(query(tmp,col)!=pos[t][m]-pos[t][i]+1){
                        r=m;
                    }else{
                        l=m+1;
                    }
                }
                ans[node[t][pos[t][l]]]=col;
                found.emplace_back(pos[t][l]);
                i=l;
            }
            for(auto i:found){
                pos[t].erase(lower_bound(pos[t].begin(),pos[t].end(),i));
            }
        }
    }
    for(int i=0;i<n;i++){
        ans[i]=ans[fp(i)];
        assert(ans[i]!=-1);
    }
    return ans;
}

Compilation message (stderr)

sphinx.cpp: In function 'std::vector<int> find_colours(int, std::vector<int>, std::vector<int>)':
sphinx.cpp:159:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |             for(int i=0;i<pos[t].size();i++){
      |                         ~^~~~~~~~~~~~~~
sphinx.cpp:163:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |                 if(query(filter,col)==node[t].size()-pos[t][i]){
sphinx.cpp:170:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |                     for(int j=0;j<node[t].size();j++){
      |                                 ~^~~~~~~~~~~~~~~

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