#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");
}
}
}
# |
결과 |
실행 시간 |
메모리 |
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 |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
25676 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
8 ms |
25676 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
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 |
- |