oj.uz

Submission #11551

# Submission time Handle Problem Language Result Execution time Memory
11551 2014-12-01T06:19:42 Z gs12117 전선 연결하기 (GA9_wire) C++
0 / 100
 160 ms 25676 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 25676 KB Output is correct
2 Correct 0 ms 25676 KB Output is correct
3 Incorrect 0 ms 25676 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 25676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 25676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 25676 KB Output is correct
2 Incorrect 160 ms 25676 KB Output isn't correct
3 Halted 0 ms 0 KB -