| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 12827 |
2015-01-09T12:41:07 Z |
ainta |
전선 연결하기 (GA9_wire) |
C++ |
|
0 ms |
24520 KB |
#include<stdio.h>
#include<algorithm>
using namespace std;
#define SZ 1048576
int n, chk[301000], num[601000];
int st[301000];
struct IdxTree{
int r, l;
}IT[SZ + SZ + 1];
struct point{
int b, e;
}w[301000];
void UDT(int x){
while (x != 1){
x >>= 1;
if (w[IT[x * 2].l].b <= w[IT[x * 2 + 1].l].b)IT[x].l = IT[x * 2].l;
else IT[x].l = IT[x * 2 + 1].l;
if (w[IT[x * 2].r].e >= w[IT[x * 2 + 1].r].e)IT[x].r = IT[x * 2].r;
else IT[x].r = IT[x * 2 + 1].r;
}
}
void Ins(int x, int a){
x += SZ;
IT[x].l = IT[x].r = a;
UDT(x);
}
void Del(int x){
x += SZ;
IT[x].l = IT[x].r = 0;
UDT(x);
}
int Left(int b, int e){
int r = 0;
b += SZ, e += SZ;
while (b <= e){
if (w[r].b > w[IT[b].l].b)r = IT[b].l;
if (w[r].b > w[IT[e].l].b)r = IT[e].l;
b = (b + 1) >> 1, e = (e - 1) >> 1;
}
return r;
}
int Right(int b, int e){
int r = 0;
b += SZ, e += SZ;
while (b <= e){
if (w[r].e < w[IT[b].r].e)r = IT[b].r;
if (w[r].e < w[IT[e].r].e)r = IT[e].r;
b = (b + 1) >> 1, e = (e - 1) >> 1;
}
return r;
}
bool Check(int ck){
int i, top = 0;
for (i = 1; i <= 2 * n; i++){
if (chk[num[i]] != ck)continue;
if (st[top] == num[i])top--;
else st[++top] = num[i];
}
if (top)return false;
return true;
}
void DFS(int a, int b){
chk[a] = b;
int i, l, r;
Del(w[a].b);
Del(w[a].e);
l = Left(w[a].b, w[a].e);
r = Right(w[a].b, w[a].e);
if (w[l].b < w[a].b)DFS(l, 3 - b);
if (w[r].e > w[a].e)DFS(r, 3 - b);
}
int main(){
int i, a, t;
scanf("%d", &n);
w[0].b = 2 * n + 1, w[1].e = 0;
for (i = 1; i <= 2 * n; i++){
scanf("%d", &a);
num[i] = a;
if (!w[a].b)w[a].b = i;
else w[a].e = i;
}
for (i = 1; i <= n; i++){
Ins(w[i].b, i);
Ins(w[i].e, i);
}
for (i = 1; i <= n; i++){
if (!chk[i]){
DFS(i, 1);
}
}
if (Check(1) && Check(2)){
for (i = 1; i <= 2 * n; i++){
if (chk[num[i]] == 1)printf("^");
else printf("v");
}
}
else printf("IMPOSSIBLE\n");
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
24520 KB |
Output is correct |
| 2 |
Correct |
0 ms |
24520 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
24520 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
