oj.uz

Submission #14355

# Submission time Handle Problem Language Result Execution time Memory
14355 2015-05-12T11:12:23 Z gs14004 전선 연결하기 (GA9_wire) C++14
61 / 100
 504 ms 65536 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[2100000];
    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[2100000];
    void init(int n){
        fill(tree,tree+2100000,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 8 ms 39888 KB Output is correct
2 Correct 4 ms 39888 KB Output is correct
3 Correct 6 ms 39888 KB Output is correct
4 Correct 4 ms 39888 KB Output is correct
5 Correct 4 ms 39888 KB Output is correct
6 Correct 4 ms 39888 KB Output is correct
7 Correct 8 ms 39888 KB Output is correct
8 Correct 8 ms 39888 KB Output is correct
9 Correct 8 ms 39888 KB Output is correct
10 Correct 8 ms 39888 KB Output is correct
11 Correct 4 ms 39888 KB Output is correct
12 Correct 8 ms 39888 KB Output is correct
13 Correct 6 ms 39888 KB Output is correct
14 Correct 4 ms 39888 KB Output is correct
15 Correct 8 ms 39888 KB Output is correct
16 Correct 8 ms 39888 KB Output is correct
17 Correct 6 ms 39888 KB Output is correct
18 Correct 5 ms 39888 KB Output is correct
19 Correct 8 ms 39888 KB Output is correct
20 Correct 8 ms 39888 KB Output is correct
21 Correct 4 ms 39888 KB Output is correct
22 Correct 4 ms 39888 KB Output is correct
23 Correct 4 ms 39888 KB Output is correct
24 Correct 8 ms 39888 KB Output is correct
25 Correct 8 ms 39888 KB Output is correct
26 Correct 8 ms 39888 KB Output is correct
27 Correct 6 ms 39888 KB Output is correct
28 Correct 8 ms 39888 KB Output is correct
29 Correct 8 ms 39888 KB Output is correct
30 Correct 6 ms 39888 KB Output is correct
31 Correct 8 ms 39888 KB Output is correct
32 Correct 8 ms 39888 KB Output is correct
33 Correct 9 ms 39888 KB Output is correct
34 Correct 8 ms 39888 KB Output is correct
35 Correct 6 ms 39888 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 40420 KB Output is correct
2 Correct 21 ms 40404 KB Output is correct
3 Correct 88 ms 43664 KB Output is correct
4 Correct 102 ms 41952 KB Output is correct
5 Correct 81 ms 41880 KB Output is correct
6 Correct 69 ms 41840 KB Output is correct
7 Correct 107 ms 43608 KB Output is correct
8 Correct 12 ms 40064 KB Output is correct
9 Correct 28 ms 40404 KB Output is correct
10 Correct 88 ms 43540 KB Output is correct
11 Correct 71 ms 41880 KB Output is correct
12 Correct 82 ms 41944 KB Output is correct
13 Correct 81 ms 41848 KB Output is correct
14 Correct 93 ms 41880 KB Output is correct
15 Correct 109 ms 41944 KB Output is correct
16 Correct 24 ms 40420 KB Output is correct
17 Correct 23 ms 40404 KB Output is correct
18 Correct 110 ms 43716 KB Output is correct
19 Correct 76 ms 41816 KB Output is correct
20 Correct 135 ms 43544 KB Output is correct
21 Correct 108 ms 41824 KB Output is correct
22 Correct 117 ms 42008 KB Output is correct
23 Correct 147 ms 43616 KB Output is correct
24 Correct 142 ms 42024 KB Output is correct
25 Correct 142 ms 44148 KB Output is correct
26 Correct 141 ms 43488 KB Output is correct
27 Correct 152 ms 48332 KB Output is correct
28 Correct 150 ms 48296 KB Output is correct
29 Correct 159 ms 48072 KB Output is correct
30 Correct 152 ms 48076 KB Output is correct

Subtask #4
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 44248 KB Output is correct
2 Correct 313 ms 44252 KB Output is correct
3 Correct 223 ms 47192 KB Output is correct
4 Correct 316 ms 48528 KB Output is correct
5 Correct 333 ms 47696 KB Output is correct
6 Correct 487 ms 56408 KB Output is correct
7 Correct 487 ms 47992 KB Output is correct
8 Correct 357 ms 47776 KB Output is correct
9 Correct 245 ms 44540 KB Output is correct
10 Correct 248 ms 47192 KB Output is correct
11 Correct 337 ms 47096 KB Output is correct
12 Correct 253 ms 44040 KB Output is correct
13 Correct 499 ms 48820 KB Output is correct
14 Correct 481 ms 54240 KB Output is correct
15 Correct 270 ms 48216 KB Output is correct
16 Correct 227 ms 44260 KB Output is correct
17 Correct 244 ms 43852 KB Output is correct
18 Correct 238 ms 44012 KB Output is correct
19 Correct 368 ms 47864 KB Output is correct
20 Correct 470 ms 47872 KB Output is correct
21 Correct 501 ms 48808 KB Output is correct
22 Correct 504 ms 59956 KB Output is correct
23 Correct 464 ms 60972 KB Output is correct
24 Memory limit exceeded 437 ms 65536 KB Memory limit exceeded
25 Halted 0 ms 0 KB -