Submission #12042

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

wire

#include <stdio.h>
#include <stack>
#include <memory.h>
using namespace std;
 
int N, A[600500], L[300500], R[300500];
stack<int> stk[2];
 
// an 2^n approach
int main() {
    scanf("%d", &N);
    for(int i = 1; i <= N+N; i++) {
        scanf("%d", &A[i]);
        if(L[A[i]]) R[A[i]] = i; else L[A[i]] = i;
    }
     
     
    for(int state = 0; state < (1<<N); state++) {
        for(int i = 0; i < 2; i++) while(!stk[i].empty()) stk[i].pop();
        bool valid = true;
        for(int i = 1; i <= N+N && valid; i++){
            int d = (state >> (A[i]-1)) & 1;
            if(i == L[A[i]]) stk[d].push(A[i]);
            else {
                if(stk[d].empty() || stk[d].top() != A[i]) valid = false;
                else stk[d].pop();
            }
        }
        if(valid) {
            for(int i = 1; i <= N+N; i++) {
                putchar(((state >> (A[i] - 1)) & 1) ? '^' : 'v');
            }
            return 0;
        }
    }
     
    puts("IMPOSSIBLE");
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 15
• Subtask 3: 0 / 37
• Subtask 4: 0 / 39