oj.uz

Submission #11541

# Submission time Handle Problem Language Result Execution time Memory
11541 2014-11-30T15:09:20 Z tncks0121 전선 연결하기 (GA9_wire) C++14
0 / 100
 1000 ms 3304 KB 
#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_ = 100500;

int N, X, A[N_ + N_];
bool used[N_];
int L[N_], R[N_];

void INVALID() {
puts("INVALID");
    exit(0);
}

int res[N_];
queue<int> que;
stack<int> stk;

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;
    }
    
    memset(used, 0, sizeof used);
    for(int st = 1; st <= N; st++) if(!used[st]) {
        que.push(st);
        res[st] = 1;
        while(!que.empty()) {
            int u = que.front(); que.pop(); used[u] = true;
            for(int v = 1; v <= N; v++) if(!used[v]) {
                if((L[u] < L[v] && L[v] < R[u] && R[u] < R[v])
                   || (L[v] < L[u] && L[u] < R[v] && R[v] < R[u])) {
                    que.push(v);
                    used[v] = true;
                    res[v] = 3 - res[u];
                }
            }
        }
    }
    
    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
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3304 KB Output is correct
2 Correct 0 ms 3304 KB Output is correct
3 Correct 0 ms 3304 KB Output is correct
4 Correct 0 ms 3304 KB Output is correct
5 Correct 0 ms 3304 KB Output is correct
6 Correct 0 ms 3304 KB Output is correct
7 Correct 0 ms 3304 KB Output is correct
8 Correct 0 ms 3304 KB Output is correct
9 Correct 0 ms 3304 KB Output is correct
10 Correct 0 ms 3304 KB Output is correct
11 Correct 0 ms 3304 KB Output is correct
12 Correct 0 ms 3304 KB Output is correct
13 Correct 0 ms 3304 KB Output is correct
14 Correct 0 ms 3304 KB Output is correct
15 Correct 0 ms 3304 KB Output is correct
16 Correct 0 ms 3304 KB Output is correct
17 Correct 0 ms 3304 KB Output is correct
18 Correct 0 ms 3304 KB Output is correct
19 Correct 0 ms 3304 KB Output is correct
20 Correct 0 ms 3304 KB Output is correct
21 Correct 0 ms 3304 KB Output is correct
22 Correct 0 ms 3304 KB Output is correct
23 Correct 0 ms 3304 KB Output is correct
24 Correct 0 ms 3304 KB Output is correct
25 Correct 0 ms 3304 KB Output is correct
26 Correct 0 ms 3304 KB Output is correct
27 Incorrect 0 ms 3304 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

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

Subtask #3
0.0 / 37.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 3304 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 3300 KB Program timed out
2 Halted 0 ms 0 KB -