제출 #1131692

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131692		StefanSebez	스핑크스 (IOI24_sphinx)	C++20	100 / 100	121 ms	8608 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e5+50;
vector<int>E[N];
bool was[N];
int par[N];
void DFS(int u){
	was[u]=true;
	for(auto i:E[u]){
		if(!was[i]) {par[i]=u;DFS(i);}
	}
}
vector<int>vtx[N];
struct DSU{
    int par[N+50];
    DSU(){Init();}
    void Init(){for(int i=0;i<N;i++) par[i]=i;}
    int FS(int u){if(par[u]==u)return u;return par[u]=FS(par[u]);}
    void US(int u,int v){u=FS(u),v=FS(v);if(u==v) return;par[u]=v;}
}dsu;
vector<int>E1[N],strana[2];
void DFSsetup(int u,int parent=-1,int depth=0){
    strana[depth&1].pb(u);
    for(auto i:E1[u]){
        if(i==parent) continue;
        DFSsetup(i,u,depth+1);
    }
}
std::vector<int> find_colours(int n, std::vector<int> X, std::vector<int> Y){
	vector<int>res(n,0);
	for(int i=0;i<X.size();i++) E[X[i]].pb(Y[i]),E[Y[i]].pb(X[i]);
	bool subtask3=true;
	for(int i=0;i<X.size();i++) if(abs(X[i]-Y[i])!=1) subtask3=false;
	if(n==2){
		for(int i=0;i<=n;i++){
			vector<int>temp;
			temp.pb(-1),temp.pb(i);
			if(perform_experiment(temp)==1){
				res[0]=i;
			}
			temp.clear();
			temp.pb(i),temp.pb(-1);
			if(perform_experiment(temp)==1){
				res[1]=i;
			}
		}
		return res;
	}
	if(subtask3){
        vector<int>temp(n);
		for(int c=0;c<n;c++){
            int ct1=0;
            for(int i=0;i<n;i++) temp[i]=c;
            for(int i=2;i<n-1;i+=2) temp[i]=-1,ct1++;
            int num=(1+2*ct1-perform_experiment(temp))>>1;
            for(int j=1;j<=num;j++){
                int ct=0;for(int i=2;i<n-1;i+=2) ct++;
                int l=1,r=ct,ind=0;
                while(l<=r){
                    int mid=l+r>>1;
                    for(int i=0;i<n;i++) temp[i]=c;
                    for(int i=2;i<=2*mid;i+=2) temp[i]=-1;
                    int x=perform_experiment(temp);
                    int y=2*mid+1-2*j;
                    if(x<=y){ind=2*mid;r=mid-1;}
                    else l=mid+1;
                }
                res[ind]=c;
            }
            ct1=0;
            for(int i=0;i<n;i++) temp[i]=c;
            for(int i=1;i<n-1;i+=2) temp[i]=-1,ct1++;
            num=(1+2*ct1-perform_experiment(temp))>>1;
            for(int j=1;j<=num;j++){
                int ct=0;
                for(int i=1;i<n-1;i+=2) ct++;
                int l=1,r=ct,ind=0;
                while(l<=r){
                    int mid=l+r>>1;
                    for(int i=0;i<n;i++) temp[i]=c;
                    for(int i=1;i<=2*mid-1;i+=2) temp[i]=-1;
                    int x=perform_experiment(temp);
                    int y=2*mid+1-2*j;
                    if(x<=y){ind=2*mid-1;r=mid-1;}
                    else l=mid+1;
                }
                res[ind]=c;
            }
            for(int i=1;i<n;i++) temp[i]=c;temp[0]=-1;
            if(perform_experiment(temp)==1) res[0]=c;
            for(int i=0;i<n-1;i++) temp[i]=c;temp[n-1]=-1;
            if(perform_experiment(temp)==1) res[n-1]=c;
        }
        return res;
	}
	if(n<=50){
		int root=0;
		for(int u=1;u<n;u++){
			for(int i=0;i<n;i++){
				for(int j=0;j<n;j++) was[j]=false;
				DFS(u);
				int v=root;
				vector<int>temp;for(int j=0;j<n;j++) temp.pb(n);
				for(int j=0;j<n;j++) was[j]=false;
				while(v!=u){
					temp[v]=i;
					was[v]=true;
					v=par[v];
				}
				temp[u]=-1;
				was[u]=true;
				//printf("%i %i: ",root,u);for(auto j:temp) printf("%i ",j);printf("\n");
				int x=perform_experiment(temp);
				int ct=0;
				for(int j=0;j<n;j++) if(!was[j]){ct++;DFS(j);}
				//printf("%i %i\n",ct,x);
				if(ct+1==x) res[u]=i;
			}
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++) was[j]=false;
			DFS(0);
			int v=1;
			vector<int>temp;for(int j=0;j<n;j++) temp.pb(n);
			for(int j=0;j<n;j++) was[j]=false;
			while(v!=0){
				temp[v]=i;
				was[v]=true;
				v=par[v];
			}
			temp[0]=-1;
			was[0]=true;
			int x=perform_experiment(temp);
			int ct=0;
			for(int j=0;j<n;j++) if(!was[j]){ct++;DFS(j);}
			if(ct+1==x) res[0]=i;
		}
		return res;
	}
	if(2*X.size()==n*(n-1)){
		for(int i=0;i<n;i++){
			res[i]=n-1;
			int l=0,r=n-1;
			while(l<=r){
				int mid=l+r>>1;
				vector<int>temp;for(int j=0;j<n;j++) temp.pb(n);
				temp[i]=-1;
				for(int j=0,ct=0;ct<=mid;j++){
					if(j==i) continue;
					temp[j]=ct;
					ct++;
				}
				int ct=0;bool was[n+10]={false};
				for(int j=0;j<n;j++){
					if(j==i) continue;
					if(!was[temp[j]]) ct++;
					was[temp[j]]=true;
				}
				//for(int j=0;j<n;j++) printf("%i ",temp[j]);printf("\n");
				int x=perform_experiment(temp);
				if(x==ct){
					res[i]=mid;
					r=mid-1;
				}
				else l=mid+1;
			}
		}
		return res;
	}
	vector<int>temp(n);
	vtx[0].pb(0);
	for(int u=1;u<n;u++){
        int num=1;
        for(int i=0;i<n;i++) temp[i]=n;
        for(int i=0;i<u;i++){for(auto j:vtx[i]) temp[j]=-1;if(!vtx[i].empty())num++;}
        temp[u]=-1;
        num-=perform_experiment(temp);
        for(int i=0;i<n;i++){was[i]=false;if(temp[i]!=n) was[i]=true;}
        for(int i=0;i<n;i++) if(temp[i]==n&&!was[i])DFS(i),num++;
        vtx[u].pb(u);
        while(num--){
            int l=0,r=u-1,nxt=u;
            while(l<=r){
                int mid=l+r>>1;
                int x=1;
                for(int i=0;i<n;i++) temp[i]=n;
                for(int i=0;i<=mid;i++){for(auto j:vtx[i]) temp[j]=-1;if(!vtx[i].empty())x++;}
                temp[u]=-1;
                x-=perform_experiment(temp);
                for(int i=0;i<n;i++){was[i]=false;if(temp[i]!=n) was[i]=true;}
                for(int i=0;i<n;i++) if(temp[i]==n&&!was[i])DFS(i),x++;
                if(x>0){nxt=mid;r=mid-1;}
                else l=mid+1;
            }
            if(nxt==u) continue;
            while(!vtx[nxt].empty()) vtx[u].pb(vtx[nxt].back()),vtx[nxt].pop_back();
        }
	}
	res.resize(n);
	for(int i=0;i<n;i++) for(auto j:vtx[i]) res[j]=i;
	//for(auto i:res) cerr<<i<<" ";cerr<<endl;
	for(int i=0;i<X.size();i++){
        int u=res[X[i]],v=res[Y[i]];
        if(u==v) continue;
        if(dsu.FS(u)==dsu.FS(v)) continue;
        dsu.US(u,v);
        E1[u].pb(v),E1[v].pb(u);
        //printf("%i %i - %i %i\n",u,v,X[i],Y[i]);
	}
	DFSsetup(n-1);
	//for(auto i:strana[0]) cerr<<i<<" ";cerr<<endl;
	//for(auto i:strana[1]) cerr<<i<<" ";cerr<<endl;
	if(strana[1].empty()){
        for(int c=0;c<n;c++){
            for(int i=0;i<n;i++) temp[i]=c;
            temp[0]=-1;
            if(perform_experiment(temp)==1){
                for(int i=0;i<n;i++) res[i]=c;
                break;
            }
        }
        return res;
	}
	vector<int>res1=res;
	for(int c=0;c<n;c++){
        for(int bit=0;bit<=1;bit++){
            int num=0;
            for(int i=0;i<n;i++) temp[i]=c;
            for(auto i:strana[bit]){for(auto j:vtx[i]) temp[j]=-1;num++;}
            num-=perform_experiment(temp);
            for(int i=0;i<n;i++){was[i]=false;if(temp[i]!=c) was[i]=true;}
            for(int i=0;i<n;i++)if(temp[i]==c&&!was[i])DFS(i),num++;
            //printf("%i %i\n",c,bit);
            int poslednji=-1;
            vector<int>izbrisi;
            while(num--){
                int l=poslednji+1,r=strana[bit].size()-1,ind=-1;
                while(l<=r){
                    int mid=l+r>>1,x=0;
                    for(int i=0;i<n;i++) temp[i]=c;
                    for(int i=poslednji+1;i<=mid;i++){for(auto j:vtx[strana[bit][i]]) temp[j]=-1;x++;}
                    x-=perform_experiment(temp);
                    for(int i=0;i<n;i++){was[i]=false;if(temp[i]!=c) was[i]=true;}
                    for(int i=0;i<n;i++)if(temp[i]==c&&!was[i])DFS(i),x++;
                    //for(auto i:temp) printf("%i ",i);printf("\n");
                    //printf("   %i %i\n",perform_experiment(temp),x);
                    if(x>0){ind=mid;r=mid-1;}
                    else l=mid+1;
                }
                if(ind==-1) break;
                for(auto i:vtx[strana[bit][ind]]) res[i]=c;
                poslednji=ind;
                izbrisi.pb(ind);
                //num-=E1[strana[bit][ind]].size();
                //printf(" %i %i\n",ind,strana[bit][ind]);
            }
            vector<int>nesto;
            for(int i=0,j=0;i<strana[bit].size();i++){
                if(j<izbrisi.size()&&i==izbrisi[j]){j++;continue;}
                nesto.pb(strana[bit][i]);
            }
            strana[bit]=nesto;
        }
	}
	return res;
}

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