oj.uz

Submission #14357

# Submission time Handle Problem Language Result Execution time Memory
14357 2015-05-12T11:13:59 Z gs14004 전선 연결하기 (GA9_wire) C++14
100 / 100
 528 ms 59684 KB 
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int,int> pi;

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

struct rmaxq{
    int lim;
    pi tree[1650000];
    void init(int n){
        for(lim = 1; lim <= n; lim <<= 1);
    }
    void add(int x, pi v){
        x += lim;
        tree[x] = v;
        while(x > 1){
            x >>= 1;
            tree[x] = max(tree[2*x],tree[2*x+1]);
        }
    }
    pi q(int s, int e){
        s += lim;
        e += lim;
        pi r(0,0);
        while(s < e){
            if(s%2 == 1) r = max(r,tree[s++]);
            if(e%2 == 0) r = max(r,tree[e--]);
            s >>= 1;
            e >>= 1;
        }
        if(s == e) r = max(r,tree[s]);
        return r;
    }
}rmaxq;

struct rminq{
    int lim;
    pi tree[1650000];
    void init(int n){
        fill(tree,tree+1650000,pi(1e9,1e9));
        for(lim = 1; lim <= n; lim <<= 1);
    }
    void add(int x, pi v){
        x += lim;
        tree[x] = v;
        while(x > 1){
            x >>= 1;
            tree[x] = min(tree[2*x],tree[2*x+1]);
        }
    }
    pi q(int s, int e){
        s += lim;
        e += lim;
        pi r(1e9,1e9);
        while(s < e){
            if(s%2 == 1) r = min(r,tree[s++]);
            if(e%2 == 0) r = min(r,tree[e--]);
            s >>= 1;
            e >>= 1;
        }
        if(s == e) r = min(r,tree[s]);
        return r;
    }
}rminq;

int lab[300005];

void dfs(int x, int l){
    lab[x] = l;
    rmaxq.add(lp[x],pi(-1,-1));
    rminq.add(rp[x],pi(1e9,1e9));
    while (1) {
        pi t = rmaxq.q(lp[x]+1,rp[x]-1);
        if(t.first > rp[x]){
            dfs(t.second,3-l);
        }
        else break;
    }
    while (1) {
        pi t = rminq.q(lp[x]+1,rp[x]-1);
        if(t.first < lp[x]){
            dfs(t.second,3-l);
        }
        else break;
    }
}

vector<int> v1, v2, st;
vector<pi> tmp;

bool eval(vector<int> &v){
    tmp.clear();
    st.clear();
    for (auto &i : v){
        tmp.push_back(pi(lp[i],i));
        tmp.push_back(pi(rp[i],-i));
    }
    sort(tmp.begin(),tmp.end());
    for (auto &i : tmp){
        if(i.second > 0){
            st.push_back(i.second);
        }
        else{
            if(st.empty() || st.back() != -i.second) return 0;
            st.pop_back();
        }
    }
    return 1;
}

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;
    }
    rmaxq.init(2*n);
    rminq.init(2*n);
    for (int i=1; i<=n; i++){
        rmaxq.add(lp[i],pi(rp[i],i));
        rminq.add(rp[i],pi(lp[i],i));
    }
    for (int i=1; i<=n; i++){
        if(!lab[i]) dfs(i,1);
    }
    for (int i=1; i<=n; i++) {
        if(lab[i] == 1){
            v1.push_back(i);
        }
        else{
            v2.push_back(i);
        }
    }
    if(!eval(v1) || !eval(v2)){
        puts("IMPOSSIBLE");
        return 0;
    }
    for (int i=1; i<=2*n; i++) {
        putchar(lab[a[i]] == 1 ? '^' : 'v');
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 32856 KB Output is correct
2 Correct 3 ms 32856 KB Output is correct
3 Correct 0 ms 32856 KB Output is correct
4 Correct 10 ms 32856 KB Output is correct
5 Correct 5 ms 32856 KB Output is correct
6 Correct 3 ms 32856 KB Output is correct
7 Correct 10 ms 32856 KB Output is correct
8 Correct 3 ms 32856 KB Output is correct
9 Correct 10 ms 32856 KB Output is correct
10 Correct 3 ms 32856 KB Output is correct
11 Correct 0 ms 32856 KB Output is correct
12 Correct 5 ms 32856 KB Output is correct
13 Correct 5 ms 32856 KB Output is correct
14 Correct 6 ms 32856 KB Output is correct
15 Correct 10 ms 32856 KB Output is correct
16 Correct 10 ms 32856 KB Output is correct
17 Correct 6 ms 32856 KB Output is correct
18 Correct 5 ms 32856 KB Output is correct
19 Correct 6 ms 32856 KB Output is correct
20 Correct 3 ms 32856 KB Output is correct
21 Correct 11 ms 32856 KB Output is correct
22 Correct 3 ms 32856 KB Output is correct
23 Correct 5 ms 32856 KB Output is correct
24 Correct 3 ms 32856 KB Output is correct
25 Correct 6 ms 32856 KB Output is correct
26 Correct 10 ms 32856 KB Output is correct
27 Correct 0 ms 32856 KB Output is correct
28 Correct 0 ms 32856 KB Output is correct
29 Correct 0 ms 32856 KB Output is correct
30 Correct 7 ms 32856 KB Output is correct
31 Correct 10 ms 32856 KB Output is correct
32 Correct 6 ms 32856 KB Output is correct
33 Correct 0 ms 32856 KB Output is correct
34 Correct 10 ms 32856 KB Output is correct
35 Correct 10 ms 32856 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 32856 KB Output is correct
2 Correct 12 ms 32856 KB Output is correct
3 Correct 7 ms 32856 KB Output is correct
4 Correct 7 ms 32856 KB Output is correct
5 Correct 5 ms 32856 KB Output is correct
6 Correct 0 ms 32856 KB Output is correct
7 Correct 3 ms 32856 KB Output is correct
8 Correct 3 ms 32856 KB Output is correct
9 Correct 7 ms 32856 KB Output is correct
10 Correct 10 ms 32856 KB Output is correct
11 Correct 3 ms 32856 KB Output is correct
12 Correct 11 ms 32856 KB Output is correct
13 Correct 11 ms 32856 KB Output is correct
14 Correct 0 ms 32856 KB Output is correct
15 Correct 11 ms 32856 KB Output is correct
16 Correct 11 ms 32856 KB Output is correct
17 Correct 5 ms 32856 KB Output is correct
18 Correct 7 ms 32856 KB Output is correct
19 Correct 7 ms 32856 KB Output is correct
20 Correct 0 ms 32856 KB Output is correct
21 Correct 12 ms 32856 KB Output is correct
22 Correct 7 ms 32856 KB Output is correct

Subtask #3
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 33388 KB Output is correct
2 Correct 27 ms 33372 KB Output is correct
3 Correct 97 ms 36636 KB Output is correct
4 Correct 107 ms 34924 KB Output is correct
5 Correct 90 ms 34848 KB Output is correct
6 Correct 82 ms 34804 KB Output is correct
7 Correct 99 ms 36576 KB Output is correct
8 Correct 17 ms 33032 KB Output is correct
9 Correct 20 ms 33372 KB Output is correct
10 Correct 87 ms 36508 KB Output is correct
11 Correct 81 ms 34848 KB Output is correct
12 Correct 77 ms 34912 KB Output is correct
13 Correct 83 ms 34816 KB Output is correct
14 Correct 85 ms 34848 KB Output is correct
15 Correct 102 ms 34916 KB Output is correct
16 Correct 29 ms 33388 KB Output is correct
17 Correct 25 ms 33372 KB Output is correct
18 Correct 106 ms 36680 KB Output is correct
19 Correct 83 ms 34784 KB Output is correct
20 Correct 134 ms 36512 KB Output is correct
21 Correct 99 ms 34792 KB Output is correct
22 Correct 104 ms 34976 KB Output is correct
23 Correct 143 ms 36576 KB Output is correct
24 Correct 135 ms 34984 KB Output is correct
25 Correct 149 ms 37116 KB Output is correct
26 Correct 147 ms 36456 KB Output is correct
27 Correct 153 ms 41300 KB Output is correct
28 Correct 158 ms 41268 KB Output is correct
29 Correct 154 ms 41040 KB Output is correct
30 Correct 157 ms 41040 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 37216 KB Output is correct
2 Correct 327 ms 37216 KB Output is correct
3 Correct 194 ms 40160 KB Output is correct
4 Correct 319 ms 41492 KB Output is correct
5 Correct 337 ms 40672 KB Output is correct
6 Correct 484 ms 49376 KB Output is correct
7 Correct 494 ms 40956 KB Output is correct
8 Correct 386 ms 40736 KB Output is correct
9 Correct 245 ms 37508 KB Output is correct
10 Correct 278 ms 40160 KB Output is correct
11 Correct 338 ms 40064 KB Output is correct
12 Correct 274 ms 37004 KB Output is correct
13 Correct 503 ms 41792 KB Output is correct
14 Correct 500 ms 47208 KB Output is correct
15 Correct 293 ms 41184 KB Output is correct
16 Correct 231 ms 37228 KB Output is correct
17 Correct 273 ms 36820 KB Output is correct
18 Correct 198 ms 36980 KB Output is correct
19 Correct 381 ms 40828 KB Output is correct
20 Correct 490 ms 40836 KB Output is correct
21 Correct 508 ms 41772 KB Output is correct
22 Correct 508 ms 52920 KB Output is correct
23 Correct 444 ms 53944 KB Output is correct
24 Correct 527 ms 59684 KB Output is correct
25 Correct 528 ms 59684 KB Output is correct