oj.uz

Submission #12144

# Submission time Handle Problem Language Result Execution time Memory
12144 2014-12-21T09:14:26 Z gs14004 전선 연결하기 (GA9_wire) C++
0 / 100
 0 ms 7688 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7688 KB Output is correct
2 Correct 0 ms 7688 KB Output is correct
3 Incorrect 0 ms 7688 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 -