답안 #14355 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
14355	2015-05-12T11:12:23 Z	gs14004	전선 연결하기 (GA9_wire)	C++14	61 / 100	504 ms	65536 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[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

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

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

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

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

답안 #14355

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 15.0 / 15.0

Subtask #3 37.0 / 37.0

Subtask #4 0.0 / 39.0

Subtask #1
9.0 / 9.0

Subtask #2
15.0 / 15.0

Subtask #3
37.0 / 37.0

Subtask #4
0.0 / 39.0