oj.uz

Submission #12099

# Submission time Handle Problem Language Result Execution time Memory
12099 2014-12-21T06:39:27 Z gs14004 전선 연결하기 (GA9_wire) C++
0 / 100
 0 ms 6516 KB 
#include <cstdio>
#include <stack>
using namespace std;

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

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(i == rp[a[i]]){
            if(str[lp[a[i]] - 1] == '^') up.pop(), str[i-1] = '^';
            else dn.pop(), str[i-1] = 'v';
        }
        else{
            int up_cost = up.empty() ? 1e9 : rp[up.top()];
            int dn_cost = dn.empty() ? 1e9 : rp[dn.top()];
            int my_cost = rp[a[i]];
            if(up_cost <= dn_cost){
                if(my_cost < up_cost){
                    up.push(a[i]);
                    str[i-1] = '^';
                }
                else if(my_cost < dn_cost){
                    dn.push(a[i]);
                    str[i-1] = 'v';
                }
                else{
                    puts("IMPOSSIBLE");
                    return 0;
                }
            }
            else{
                if(my_cost < dn_cost){
                    dn.push(a[i]);
                    str[i-1] = 'v';
                }
                else if(my_cost < up_cost){
                    up.push(a[i]);
                    str[i-1] = '^';
                }
                else{
                    puts("IMPOSSIBLE");
                    return 0;
                }
            }
        }
    }
    puts(str);
}

Subtask #1
0.0 / 9.0

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #3
0.0 / 37.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #4
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -