답안 #14356 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
14356	2015-05-12T11:13:37 Z	gs14004	전선 연결하기 (GA9_wire)	C++14	100 / 100	542 ms	59688 KB

wire

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #14356

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 15.0 / 15.0

Subtask #3 37.0 / 37.0

Subtask #4 39.0 / 39.0

Subtask #1
9.0 / 9.0

Subtask #2
15.0 / 15.0

Subtask #3
37.0 / 37.0

Subtask #4
39.0 / 39.0