oj.uz

Submission #14356

# Submission time Handle Problem Language Result Execution time Memory
14356 2015-05-12T11:13:37 Z gs14004 전선 연결하기 (GA9_wire) C++14
100 / 100
 542 ms 59688 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 5 ms 32856 KB Output is correct
2 Correct 7 ms 32856 KB Output is correct
3 Correct 5 ms 32856 KB Output is correct
4 Correct 5 ms 32856 KB Output is correct
5 Correct 6 ms 32856 KB Output is correct
6 Correct 6 ms 32856 KB Output is correct
7 Correct 10 ms 32856 KB Output is correct
8 Correct 6 ms 32856 KB Output is correct
9 Correct 10 ms 32856 KB Output is correct
10 Correct 6 ms 32856 KB Output is correct
11 Correct 6 ms 32856 KB Output is correct
12 Correct 10 ms 32856 KB Output is correct
13 Correct 10 ms 32856 KB Output is correct
14 Correct 0 ms 32856 KB Output is correct
15 Correct 5 ms 32856 KB Output is correct
16 Correct 3 ms 32856 KB Output is correct
17 Correct 6 ms 32856 KB Output is correct
18 Correct 3 ms 32856 KB Output is correct
19 Correct 10 ms 32856 KB Output is correct
20 Correct 0 ms 32856 KB Output is correct
21 Correct 3 ms 32856 KB Output is correct
22 Correct 10 ms 32856 KB Output is correct
23 Correct 9 ms 32856 KB Output is correct
24 Correct 10 ms 32856 KB Output is correct
25 Correct 10 ms 32856 KB Output is correct
26 Correct 6 ms 32856 KB Output is correct
27 Correct 5 ms 32856 KB Output is correct
28 Correct 5 ms 32856 KB Output is correct
29 Correct 10 ms 32856 KB Output is correct
30 Correct 6 ms 32856 KB Output is correct
31 Correct 0 ms 32856 KB Output is correct
32 Correct 10 ms 32856 KB Output is correct
33 Correct 0 ms 32856 KB Output is correct
34 Correct 11 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 10 ms 32856 KB Output is correct
2 Correct 8 ms 32856 KB Output is correct
3 Correct 7 ms 32856 KB Output is correct
4 Correct 10 ms 32856 KB Output is correct
5 Correct 8 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 5 ms 32856 KB Output is correct
9 Correct 0 ms 32856 KB Output is correct
10 Correct 10 ms 32856 KB Output is correct
11 Correct 7 ms 32856 KB Output is correct
12 Correct 0 ms 32856 KB Output is correct
13 Correct 11 ms 32856 KB Output is correct
14 Correct 3 ms 32856 KB Output is correct
15 Correct 7 ms 32856 KB Output is correct
16 Correct 11 ms 32856 KB Output is correct
17 Correct 7 ms 32856 KB Output is correct
18 Correct 7 ms 32856 KB Output is correct
19 Correct 3 ms 32856 KB Output is correct
20 Correct 0 ms 32856 KB Output is correct
21 Correct 0 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 23 ms 33388 KB Output is correct
2 Correct 21 ms 33372 KB Output is correct
3 Correct 91 ms 36636 KB Output is correct
4 Correct 93 ms 34920 KB Output is correct
5 Correct 84 ms 34848 KB Output is correct
6 Correct 74 ms 34804 KB Output is correct
7 Correct 107 ms 36576 KB Output is correct
8 Correct 17 ms 33032 KB Output is correct
9 Correct 25 ms 33372 KB Output is correct
10 Correct 99 ms 36512 KB Output is correct
11 Correct 87 ms 34848 KB Output is correct
12 Correct 76 ms 34912 KB Output is correct
13 Correct 90 ms 34816 KB Output is correct
14 Correct 93 ms 34848 KB Output is correct
15 Correct 106 ms 34912 KB Output is correct
16 Correct 24 ms 33388 KB Output is correct
17 Correct 27 ms 33372 KB Output is correct
18 Correct 104 ms 36680 KB Output is correct
19 Correct 74 ms 34784 KB Output is correct
20 Correct 131 ms 36512 KB Output is correct
21 Correct 100 ms 34792 KB Output is correct
22 Correct 110 ms 34972 KB Output is correct
23 Correct 154 ms 36580 KB Output is correct
24 Correct 109 ms 34992 KB Output is correct
25 Correct 150 ms 37120 KB Output is correct
26 Correct 137 ms 36456 KB Output is correct
27 Correct 159 ms 41300 KB Output is correct
28 Correct 155 ms 41264 KB Output is correct
29 Correct 159 ms 41044 KB Output is correct
30 Correct 160 ms 41040 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 37216 KB Output is correct
2 Correct 324 ms 37220 KB Output is correct
3 Correct 224 ms 40160 KB Output is correct
4 Correct 343 ms 41496 KB Output is correct
5 Correct 340 ms 40668 KB Output is correct
6 Correct 488 ms 49376 KB Output is correct
7 Correct 501 ms 40960 KB Output is correct
8 Correct 380 ms 40740 KB Output is correct
9 Correct 265 ms 37504 KB Output is correct
10 Correct 265 ms 40160 KB Output is correct
11 Correct 338 ms 40064 KB Output is correct
12 Correct 262 ms 37004 KB Output is correct
13 Correct 502 ms 41792 KB Output is correct
14 Correct 484 ms 47208 KB Output is correct
15 Correct 261 ms 41184 KB Output is correct
16 Correct 234 ms 37224 KB Output is correct
17 Correct 255 ms 36816 KB Output is correct
18 Correct 198 ms 36976 KB Output is correct
19 Correct 381 ms 40824 KB Output is correct
20 Correct 495 ms 40840 KB Output is correct
21 Correct 494 ms 41776 KB Output is correct
22 Correct 520 ms 52924 KB Output is correct
23 Correct 511 ms 53940 KB Output is correct
24 Correct 526 ms 59680 KB Output is correct
25 Correct 542 ms 59688 KB Output is correct