Submission #11551

#	Time	Username	Problem	Language	Result	Execution time	Memory
11551		gs12117	전선 연결하기 (GA9_wire)	C++98	0 / 100	160 ms	25676 KiB

wire

#include<stdio.h>
int n;
int a[600100];
int b[300100][2];
int chk[300100];
int uft[300100][2];
int it[1<<21];
int itm[1<<21];
int flag;
int uftf(int x){
	if(uft[x][0]==x)return x;
	uftf(uft[x][0]);
	uft[x][1]^=uft[uft[x][0]][1];
	uft[x][0]=uft[uft[x][0]][0];
}
void push(int loc,int val){
	loc+=1<<20;
	itm[loc]=1;
	while(loc!=0){
		it[loc]=val;
		loc/=2;
	}
}
void pop(int loc){
	loc+=1<<20;
	it[loc]=0;
	loc/=2;
	while(loc!=0){
		if(it[loc*2]!=0)it[loc]=it[loc*2];
		else it[loc]=it[loc*2+1];
		loc/=2;
	}
}
void link(int pa,int pb,int val){
	if(uftf(pa)==uftf(pb)){
		if((uft[pa][1]^uft[pb][1])!=val)flag=1;
	}
	else{
		uft[uft[pb][0]][1]=(val^uft[pa][1]^uft[pb][1]);
		uft[uft[pb][0]][0]=uft[pa][0];
	}
}
void merge(int loc){
	if(it[loc]==0||itm[loc]==1)return;
	merge(loc*2);
	merge(loc*2+1);
	itm[loc]=1;
	if(it[loc*2]!=0&&it[loc*2+1]!=0){
		link(it[loc*2],it[loc*2+1],0);
	}
}
void calc(int start,int end,int p){
	start+=1<<20;
	end+=1<<20;
	while(start<=end){
		if(start%2==1){
			merge(start);
			if(it[start]!=0)link(p,it[start],1);
			start++;
		}
		if(end%2==0){
			merge(end);
			if(it[end]!=0)link(p,it[end],1);
			end--;
		}
		start/=2;
		end/=2;
	}
}
int main(){
	int i;
	scanf("%d",&n);
	for(i=0;i<2*n;i++){
		scanf("%d",&a[i]);
		b[a[i]][chk[a[i]]]=i;
		chk[a[i]]++;
	}
	for(i=1;i<=n;i++){
		uft[i][0]=i;
		uft[i][1]=0;
	}
	for(i=1;i<=n;i++){
		push(b[i][0],i);
	}
	flag=0;
	for(i=0;i<2*n;i++){
		if(b[a[i]][1]==i){
			pop(b[a[i]][0]);
			calc(b[a[i]][0],b[a[i]][1],a[i]);
		}
	}
	if(flag==1){
		printf("IMPOSSIBLE");
	}
	else{
		for(i=1;i<=n;i++){
			uftf(i);
		}
		for(i=0;i<2*n;i++){
			if(uft[a[i]][1]==0)printf("^");
			else printf("v");
		}
	}
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 15
• Subtask 3: 0 / 37
• Subtask 4: 0 / 39