Submission #1213485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213485		user736482	Sphinx's Riddle (IOI24_sphinx)	C++20	64 / 100	1550 ms	2476 KiB

sphinx

#include "sphinx.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 998244353
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
vector<ll> g[300],g2[300];
bool col[300],odw[300];
ll par[300];

void dfs(ll v,bool cl){
    if(odw[v])return;
    odw[v]=1;
    col[v]=cl;
    for(ll i : g2[v])dfs(i,!cl);
}
ll comps(vector<ll>v){
    sort(v.begin(),v.end());
    queue<ll>q;
    bool odw[300];
    for(ll i : v)odw[i]=0;
    ll res=0;
    for(ll i : v){
        if(odw[i]==0){
            res++;
            q.push(i);
            while(!q.empty()){
                auto pom=q.front();
                q.pop();
                if(!odw[pom] && lower_bound(v.begin(),v.end(),pom)!=v.end() && *lower_bound(v.begin(),v.end(),pom)==pom){
                    odw[pom]=1;
                    for(ll j : g[pom])q.push(j);
                }
            }
        }
    }
    return res;
}
ll comps2(vector<vector<ll>>v){
    vector<ll>v2;
    for(auto i : v)for(auto j : i )v2.pb(j);return comps(v2);
}
ll zap(vector<ll>v,ll n,ll cl){
    vector<int>pm;
    pm.resize(n);
    for(ll i=0;i<n;i++){pm[i]=n;if(col[par[i]])pm[i]=cl;}
    for(ll i : v)pm[i]=-1;
    vector<ll>v2;
    for(ll i=0;i<n;i++)if(pm[i]==n)v2.pb(i);
    return perform_experiment(pm)-comps(v2);
}
ll zap2(vector<vector<ll>>v,ll n,ll cl){
    vector<ll>v2;
    for(vector<ll> i : v)for(ll j : i)v2.pb(j);
    return zap(v2,n,cl);
}
vector<int>find_colours(int n,vector<int>x,vector<int>y){
    for(ll i=0;i<n+7;i++){g[i].clear();g2[i].clear();odw[i]=0;}
    bool kn[300][300];
    bool kn2[300][300];
    for(ll i=0;i<x.size();i++){
        g[x[i]].pb(y[i]);
        g[y[i]].pb(x[i]);
        kn[x[i]][y[i]]=1;
        kn[y[i]][x[i]]=1;
    }
    vector<vector<ll>>cmp={{0}};
    vector<ll>v;
    for(ll i=1;i<n;i++){
        cmp.pb({i});
        ll pm=zap2(cmp,n,-1);
        cmp.pop_back();
        vector<ll>ak={i};
        pm=cmp.size()+1-pm;
        for(ll k=0;k<pm;k++){
            ll pocz=0;
            ll kon=cmp.size()-1;
            while(pocz!=kon){
                ll mid=(pocz+kon)/2;
                vector<vector<ll>>query={ak};
                for(ll j=pocz;j<=mid;j++)query.pb(cmp[j]);
                if(zap2(query,n,-1)!=query.size()) kon=mid;
                else pocz=mid+1;
            }
            swap(cmp[pocz],cmp.back());
            for(ll j : cmp.back())ak.pb(j);
            cmp.pop_back();
        }
        cmp.pb(ak);
    }
    vector<int>ans;
    ans.resize(n);
    if(cmp.size()==1){
        vector<int>ak;
        ak.resize(n);
        for(ll i=0;i<n;i++)ak[i]=-1;
        for(ll i=0;i<n;i++){
            ak[0]=i;
            if(perform_experiment(ak)==1){
                for(ll j=0;j<n;j++)ans[j]=i;return ans;
            }
        }
    }
    for(ll i=0;i<cmp.size();i++){
        for(ll j : cmp[i])par[j]=i;
        for(ll j=0;j<cmp.size();j++){
            for(ll a : cmp[i]) for(ll b : cmp[j]) if(kn[a][b])kn2[i][j]=1;
            if(kn2[i][j])g2[i].pb(j);
        }
    }
    dfs(0,0);
    v.clear();
    for(ll i=0;i<cmp.size();i++)if(!col[i])v.pb(i);
    for(ll akcol=0;akcol<n;akcol++){
        vector<vector<ll>>v2,ak;
        for(ll i=0;i<cmp.size();i++)if(col[i])ak.pb(cmp[i]);
        auto akold=ak;
        for(ll j : v)v2.pb(cmp[j]);
        ll pom=zap2(v2,n,akcol);
        while(comps2(ak)+cmp.size()-ak.size()!=pom){
            ll pocz=0;
            ll kon=v2.size()-1;
            while(pocz!=kon){
                ll mid=(pocz+kon)/2;
                vector<vector<ll>>query;
                for(ll i=pocz;i<=mid;i++)query.pb(v2[i]);
                if(zap2(query,n,akcol)!=comps2(akold)+query.size())kon=mid;
                else pocz=mid+1;
            }
            ak.pb(v2[pocz]);
            swap(v2[pocz],v2.back());
            for(ll i : v2.back())ans[i]=akcol;
            v2.pop_back();
        }
    }
    for(ll i=0;i<cmp.size();i++)col[i]^=1;
    v.clear();
    for(ll i=0;i<cmp.size();i++)if(!col[i])v.pb(i);
    for(ll akcol=0;akcol<n;akcol++){
        vector<vector<ll>>v2,ak;
        for(ll i=0;i<cmp.size();i++)if(col[i])ak.pb(cmp[i]);
        auto akold=ak;
        for(ll j : v)v2.pb(cmp[j]);
        ll pom=zap2(v2,n,akcol);
        while(comps2(ak)+cmp.size()-ak.size()!=pom){
            ll pocz=0;
            ll kon=v2.size()-1;
            while(pocz!=kon){
                ll mid=(pocz+kon)/2;
                vector<vector<ll>>query;
                for(ll i=pocz;i<=mid;i++)query.pb(v2[i]);
                if(zap2(query,n,akcol)!=comps2(akold)+query.size())kon=mid;
                else pocz=mid+1;
            }
            ak.pb(v2[pocz]);
            swap(v2[pocz],v2.back());
            for(ll i : v2.back())ans[i]=akcol;
            v2.pop_back();
        }
    }
    return ans;
}

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