Submission #12144

#	Time	Username	Problem	Language	Result	Execution time	Memory
12144		gs14004	전선 연결하기 (GA9_wire)	C++98	0 / 100	0 ms	7688 KiB

wire

#include <cstdio>
#include <stack>
#include <cassert>
using namespace std;

int n,a[600005];
int lp[300005], rp[300005];
char str[600005];
int occu[300005];

stack<int> up, dn;

int main(){
    scanf("%d",&n);
    for (int i=1; i<=2*n; i++) {
        scanf("%d",&a[i]);
        if(lp[a[i]] == 0) lp[a[i]] = i;
        else rp[a[i]] = i;
    }
    for (int i=1; i<=2*n; i++) {
        if(occu[a[i]]){
            if(occu[a[i]] == 2) assert(rp[up.top()] == i), up.pop(), str[i-1] = '^';
            else assert(rp[dn.top()] == i), dn.pop(), str[i-1] = 'v';
        }
        else{
            int up_cost = up.empty() ? 987654321 : rp[up.top()];
            int dn_cost = dn.empty() ? 987654321 : rp[dn.top()];
            int my_cost = rp[a[i]];
            if(up_cost <= dn_cost){
                if(my_cost < up_cost){
                    up.push(a[i]);
                    occu[a[i]] = 2;
                    str[i-1] = '^';
                }
                else if(my_cost < dn_cost){
                    dn.push(a[i]);
                    occu[a[i]] = 1;
                    str[i-1] = 'v';
                }
                else{
                    printf("IMPOSSIBLE");
                    return 0;
                }
            }
            else{
                if(my_cost < dn_cost){
                    dn.push(a[i]);
                    occu[a[i]] = 1;
                    str[i-1] = 'v';
                }
                else if(my_cost < up_cost){
                    up.push(a[i]);
                    occu[a[i]] = 2;
                    str[i-1] = '^';
                }
                else{
                    printf("IMPOSSIBLE");
                    return 0;
                }
            }
        }
    }
    puts(str);
}

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