oj.uz

Submission #18426

# Submission time Handle Problem Language Result Execution time Memory
18426 2016-02-01T11:45:17 Z tlwpdus 전선 연결하기 (GA9_wire) C++
24 / 100
 4 ms 3308 KB 
#include<stdio.h>
#include<algorithm>
#include<set>
#include<vector>
#include<string.h>

#define MAXN 5010

using namespace std;

vector<int> lis[MAXN];

struct segtree {
    set<int> tree[8*MAXN];
    int key;
    void init(int n) {
        key = 1;
        while(key<n) key*=2;
    }
    void update(int idx, int val, int type) {
        idx+=key;
        while(idx>0) {
            if (type==1) tree[idx].insert(val);
            else tree[idx].erase(val);
            idx/=2;
        }
    }
    void put(int idx, int v) {
        set<int>::iterator it = tree[idx].begin();
        for (;it!=tree[idx].end();it++) {
            lis[v].push_back(*it);
            lis[*it].push_back(v);
        }
    }
    void query(int s, int e, int v) {
        s+=key;
        e+=key;
        while(s<=e) {
            if (s%2==1) put(s++,v);
            if (e%2==0) put(e--,v);
            s >>= 1;
            e >>= 1;
        }
    }
} seg;

int n;
int arr[2*MAXN];
int loc[MAXN][2];
int ud[MAXN];

bool dfs(int here, int st) {
    if (ud[here]==-st) return false;
    else if (ud[here]!=0) return true;
    ud[here] = st;
    int i;
    for (i=0;i<lis[here].size();i++) {
        int there = lis[here][i];
        if (!dfs(there,-st)) return false;
    }
    return true;
}

void process() {
    int i, j;
    seg.init(2*n+2);
    for (i=0;i<2*n;i++) {
        if (loc[arr[i]][0]==i) {
            seg.query(loc[arr[i]][0],loc[arr[i]][1],arr[i]);
            seg.update(loc[arr[i]][1],arr[i],1);
        }
        else seg.update(loc[arr[i]][1],arr[i],0);
    }
    for (i=0;i<n;i++) if (ud[i]==0) {
        if (!dfs(i,1)) {
            printf("IMPOSSIBLE\n");
            return;
        }
    }
    for (i=0;i<2*n;i++) {
        if (ud[arr[i]]==1) printf("^");
        else printf("v");
    }
    printf("\n");
}

void input() {
    int i;
    scanf("%d",&n);
    memset(loc,-1,sizeof(loc));
    for (i=0;i<2*n;i++) {
        scanf("%d",&arr[i]);
        arr[i]--;
        if (loc[arr[i]][0]==-1) loc[arr[i]][0] = i;
        else loc[arr[i]][1] = i;
    }
}

int main() {
    input();
    process();
    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
0.0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 3304 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -