Submission #18426

#	Time	Username	Problem	Language	Result	Execution time	Memory
18426		tlwpdus	전선 연결하기 (GA9_wire)	C++98	24 / 100	4 ms	3308 KiB

wire

#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 / 9
• Subtask 2: 15 / 15
• Subtask 3: 0 / 37
• Subtask 4: 0 / 39