답안 #11546 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
11546	2014-11-30T16:52:15 Z	tncks0121	전선 연결하기 (GA9_wire)	C++14	100 / 100	760 ms	52668 KB

wire

#define _CRT_SECURE_NO_WARNINGS
 
#include <stdio.h>
#include <stack>
#include <memory.h>
#include <assert.h>
#include <stdlib.h>
#include <algorithm>
#include <set>
#include <queue>
#include <functional>
 
using namespace std;
 
const int N_ = 300500;
 
int N, X, A[N_ + N_];
bool used[N_];
int L[N_], R[N_];
 
vector<int> inside[N_];
queue<int> que;
queue<int> cand;
set<int> rpos;
stack<int> stk;
 
void INVALID() {
    puts("IMPOSSIBLE");
    exit(0);
}
 
int res[N_];
 
const int LEAF = 262144*4;
int tree1[N_ + N_ + LEAF];
int tree2[N_ + N_ + LEAF];
 
void upd(int *tree, int x, int v) {
    tree[x += LEAF] = v;
    while (x >>= 1) tree[x] = max(tree[x + x], tree[x + x + 1]);
}
 
int query(int *tree, int x, int y) {
    x += LEAF; y += LEAF;
    int ret = -(int)1e7;
    while (x <= y) {
        if ((x & 1) == 1) ret = max(ret, tree[x]);
        if ((y & 1) == 0) ret = max(ret, tree[y]);
        x = (x + 1) >> 1;
        y = (y - 1) >> 1;
    }
    return ret;
}
void que_push(int v, int r = 1) {
    if (used[v]) return;
    que.push(v); res[v] = r; used[v] = true;
    upd(tree1, L[v], 0);
    upd(tree2, R[v], -(int)1e7);
}
 
 
int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
     
    scanf("%d", &N);
    X = N + N;
    for (int i = 1; i <= X; i++) {
        scanf("%d", A + i);
        if (!used[A[i]]) L[A[i]] = i; else R[A[i]] = i;
        used[A[i]] = true;
    }
     
    fill(tree2, tree2 + LEAF + X + 10, -(int)1e7);
    for (int i = 1; i <= N; i++) {
        upd(tree1, L[i], R[i]);
        upd(tree2, R[i], -L[i]);
    }
     
    memset(used, 0, sizeof used);
    for (int i = 1; i <= X; i++) {
        int a = A[i];
        if (L[a] == i) {
            set<int>::iterator it = rpos.lower_bound(R[a]);
            if (it != rpos.end()) inside[A[*it]].push_back(a);
            else cand.push(a);
            rpos.insert(R[a]);
        }
        else {
            rpos.erase(R[a]);
        }
    }
     
    memset(used, 0, sizeof used);
     
    int cnt = 0;
    while (cnt < N) {
        que_push(cand.front()); cand.pop();
        while (!que.empty()) {
            int u = que.front(); que.pop(); ++cnt;
             
            // 1. L[x] < L[u] < R[x] < R[u]
            for (int r; (r = query(tree1, 1, L[u])) > 0;) {
                if (r < L[u]) break;
                que_push(A[r], 3 - res[u]);
            }
             
            // 2. L[u] < L[x] < R[u] < R[x]
            for (int l; (l = -query(tree2, R[u], X)) <= X;) {
                if (R[u] < l) break;
                que_push(A[l], 3 - res[u]);
            }
             
            for (int i = 0; i < inside[u].size(); i++) {
                cand.push(inside[u][i]);
            }
        }
    }
     
    for (int cur = 1; cur <= 2; cur++) {
        memset(used, 0, sizeof used);
        while (!stk.empty()) stk.pop();
         
        for (int i = 1; i <= X; i++) if (res[A[i]] == cur) {
            if (!used[A[i]]) {
                used[A[i]] = true;
                stk.push(A[i]);
            }
            else {
                if (stk.top() != A[i]) INVALID();
                stk.pop();
            }
        }
    }
     
    for (int i = 1; i <= X; i++) printf("%c", res[A[i]] == 1 ? '^' : 'v');
    return 0;
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	27340 KB	Output is correct
2	Correct	0 ms	27340 KB	Output is correct
3	Correct	8 ms	27340 KB	Output is correct
4	Correct	4 ms	27340 KB	Output is correct
5	Correct	4 ms	27340 KB	Output is correct
6	Correct	0 ms	27340 KB	Output is correct
7	Correct	4 ms	27340 KB	Output is correct
8	Correct	0 ms	27340 KB	Output is correct
9	Correct	4 ms	27340 KB	Output is correct
10	Correct	4 ms	27340 KB	Output is correct
11	Correct	0 ms	27340 KB	Output is correct
12	Correct	0 ms	27340 KB	Output is correct
13	Correct	0 ms	27340 KB	Output is correct
14	Correct	0 ms	27340 KB	Output is correct
15	Correct	4 ms	27340 KB	Output is correct
16	Correct	4 ms	27340 KB	Output is correct
17	Correct	0 ms	27340 KB	Output is correct
18	Correct	4 ms	27340 KB	Output is correct
19	Correct	0 ms	27340 KB	Output is correct
20	Correct	4 ms	27340 KB	Output is correct
21	Correct	0 ms	27340 KB	Output is correct
22	Correct	4 ms	27340 KB	Output is correct
23	Correct	4 ms	27340 KB	Output is correct
24	Correct	8 ms	27340 KB	Output is correct
25	Correct	4 ms	27340 KB	Output is correct
26	Correct	0 ms	27340 KB	Output is correct
27	Correct	8 ms	27340 KB	Output is correct
28	Correct	0 ms	27340 KB	Output is correct
29	Correct	4 ms	27340 KB	Output is correct
30	Correct	4 ms	27340 KB	Output is correct
31	Correct	8 ms	27340 KB	Output is correct
32	Correct	0 ms	27340 KB	Output is correct
33	Correct	4 ms	27340 KB	Output is correct
34	Correct	0 ms	27340 KB	Output is correct
35	Correct	8 ms	27340 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	27340 KB	Output is correct
2	Correct	4 ms	27340 KB	Output is correct
3	Correct	8 ms	27340 KB	Output is correct
4	Correct	8 ms	27340 KB	Output is correct
5	Correct	4 ms	27340 KB	Output is correct
6	Correct	4 ms	27340 KB	Output is correct
7	Correct	0 ms	27340 KB	Output is correct
8	Correct	4 ms	27340 KB	Output is correct
9	Correct	4 ms	27340 KB	Output is correct
10	Correct	4 ms	27340 KB	Output is correct
11	Correct	0 ms	27340 KB	Output is correct
12	Correct	0 ms	27340 KB	Output is correct
13	Correct	4 ms	27340 KB	Output is correct
14	Correct	0 ms	27340 KB	Output is correct
15	Correct	4 ms	27340 KB	Output is correct
16	Correct	4 ms	27340 KB	Output is correct
17	Correct	0 ms	27340 KB	Output is correct
18	Correct	0 ms	27340 KB	Output is correct
19	Correct	0 ms	27340 KB	Output is correct
20	Correct	8 ms	27340 KB	Output is correct
21	Correct	0 ms	27340 KB	Output is correct
22	Correct	8 ms	27340 KB	Output is correct

Subtask #3
37.0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	27604 KB	Output is correct
2	Correct	20 ms	27604 KB	Output is correct
3	Correct	108 ms	29188 KB	Output is correct
4	Correct	120 ms	28920 KB	Output is correct
5	Correct	92 ms	28524 KB	Output is correct
6	Correct	84 ms	28264 KB	Output is correct
7	Correct	124 ms	28788 KB	Output is correct
8	Correct	8 ms	27340 KB	Output is correct
9	Correct	12 ms	27472 KB	Output is correct
10	Correct	88 ms	28792 KB	Output is correct
11	Correct	92 ms	28524 KB	Output is correct
12	Correct	84 ms	28392 KB	Output is correct
13	Correct	96 ms	28396 KB	Output is correct
14	Correct	96 ms	28524 KB	Output is correct
15	Correct	128 ms	28660 KB	Output is correct
16	Correct	28 ms	27604 KB	Output is correct
17	Correct	28 ms	27604 KB	Output is correct
18	Correct	100 ms	29452 KB	Output is correct
19	Correct	76 ms	28524 KB	Output is correct
20	Correct	152 ms	29056 KB	Output is correct
21	Correct	120 ms	28660 KB	Output is correct
22	Correct	128 ms	28792 KB	Output is correct
23	Correct	164 ms	29188 KB	Output is correct
24	Correct	164 ms	29316 KB	Output is correct
25	Correct	168 ms	29316 KB	Output is correct
26	Correct	164 ms	29056 KB	Output is correct
27	Correct	180 ms	34336 KB	Output is correct
28	Correct	192 ms	34336 KB	Output is correct
29	Correct	192 ms	35656 KB	Output is correct
30	Correct	196 ms	35656 KB	Output is correct

Subtask #4
39.0 / 39.0

#	결과	실행 시간	메모리	Grader output
1	Correct	268 ms	30376 KB	Output is correct
2	Correct	416 ms	31296 KB	Output is correct
3	Correct	276 ms	30240 KB	Output is correct
4	Correct	396 ms	31296 KB	Output is correct
5	Correct	448 ms	31560 KB	Output is correct
6	Correct	600 ms	33012 KB	Output is correct
7	Correct	668 ms	33148 KB	Output is correct
8	Correct	536 ms	31956 KB	Output is correct
9	Correct	332 ms	30504 KB	Output is correct
10	Correct	360 ms	30772 KB	Output is correct
11	Correct	420 ms	31168 KB	Output is correct
12	Correct	336 ms	30636 KB	Output is correct
13	Correct	652 ms	33148 KB	Output is correct
14	Correct	576 ms	32356 KB	Output is correct
15	Correct	312 ms	30772 KB	Output is correct
16	Correct	284 ms	30504 KB	Output is correct
17	Correct	356 ms	30636 KB	Output is correct
18	Correct	312 ms	30384 KB	Output is correct
19	Correct	496 ms	31824 KB	Output is correct
20	Correct	664 ms	33148 KB	Output is correct
21	Correct	664 ms	33148 KB	Output is correct
22	Correct	684 ms	48508 KB	Output is correct
23	Correct	728 ms	48496 KB	Output is correct
24	Correct	720 ms	52668 KB	Output is correct
25	Correct	760 ms	52668 KB	Output is correct

답안 #11546

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 15.0 / 15.0

Subtask #3 37.0 / 37.0

Subtask #4 39.0 / 39.0

Subtask #1
9.0 / 9.0

Subtask #2
15.0 / 15.0

Subtask #3
37.0 / 37.0

Subtask #4
39.0 / 39.0