Submission #11541

#	Time	Username	Problem	Language	Result	Execution time	Memory
11541		tncks0121	전선 연결하기 (GA9_wire)	C++14	0 / 100	1000 ms	3304 KiB

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_ = 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 / 9
• Subtask 2: 0 / 15
• Subtask 3: 0 / 37
• Subtask 4: 0 / 39