답안 #12762 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
12762	2015-01-02T17:34:37 Z	dohyun0324	전선 연결하기 (GA9_wire)	C++	61 / 100	1000 ms	51876 KB

wire

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int max(int x,int y)
{
    if(x>y) return x;
    return y;
}
int min(int x,int y)
{
    if(x>y) return y;
    return x;
}
int n;
int p,t=1,a[600010],ch[600010],top,q[2500010],s[600010],e[600010],dap[600010],f,r,treeb[2500010],treef[2500010],tree[2500010];
int top2;
struct data
{
    int k,x,y,sw;
}arr[100];
void update(int x,int gap)
{
    int s=x+t-1;
    tree[s]=gap;
    s/=2;
    while(s>0){
        tree[s]=max(tree[s*2],tree[s*2+1]);
        s/=2;
    }
}
void updatef(int x,int gap)
{
    int s=x+t-1;
    treef[s]=gap;
    s/=2;
    while(s>0){
        treef[s]=min(treef[s*2],treef[s*2+1]);
        s/=2;
    }
}
void updateb(int x,int gap)
{
    int s=x+t-1;
    treeb[s]=gap;
    s/=2;
    while(s>0){
        treeb[s]=max(treeb[s*2],treeb[s*2+1]);
        s/=2;
    }
}
int queryf(int x,int y,int k,int s,int e)
{
    top2=0;
    if(s>e) return 2147483647;
    int mini=2147483647;
    top2++; arr[top2].x=x; arr[top2].y=y; arr[top2].k=k; arr[top2].sw=0;
    while(top2>0)
    {
        x=arr[top2].x; y=arr[top2].y; k=arr[top2].k;
        if(s<=x && y<=e){mini=min(treef[k],mini), top2--; continue;}
        if(s>y || e<x){top2--; continue;}
        if(arr[top2].sw==0)
        {
            arr[top2].sw=1;
            top2++; arr[top2].x=x; arr[top2].y=(x+y)/2; arr[top2].k=k*2; arr[top2].sw=0;
        }
        else if(arr[top2].sw==1)
        {
            arr[top2].sw=2;
            top2++; arr[top2].x=(x+y)/2+1; arr[top2].y=y; arr[top2].k=k*2+1; arr[top2].sw=0;
        }
        else top2--;
    }
    return mini;
}
int queryb(int x,int y,int k,int s,int e)
{
    top2=0;
    if(s>e) return 0;
    int maxi=0;
    top2++; arr[top2].x=x; arr[top2].y=y; arr[top2].k=k; arr[top2].sw=0;
    while(top2>0)
    {
        x=arr[top2].x; y=arr[top2].y; k=arr[top2].k;
        if(s<=x && y<=e){maxi=max(treeb[k],maxi), top2--; continue;}
        if(s>y || e<x){top2--; continue;}
        if(arr[top2].sw==0)
        {
            arr[top2].sw=1;
            top2++; arr[top2].x=x; arr[top2].y=(x+y)/2; arr[top2].k=k*2; arr[top2].sw=0;
        }
        else if(arr[top2].sw==1)
        {
            arr[top2].sw=2;
            top2++; arr[top2].x=(x+y)/2+1; arr[top2].y=y; arr[top2].k=k*2+1; arr[top2].sw=0;
        }
        else top2--;
    }
    return maxi;
}
int query(int x,int y,int k,int s,int e)
{
    top2=0;
    if(s>e) return 0;
    int maxi=0;
    top2++; arr[top2].x=x; arr[top2].y=y; arr[top2].k=k; arr[top2].sw=0;
    while(top2>0)
    {
        x=arr[top2].x; y=arr[top2].y; k=arr[top2].k;
        if(s<=x && y<=e){maxi=max(tree[k],maxi), top2--; continue;}
        if(s>y || e<x){top2--; continue;}
        if(arr[top2].sw==0)
        {
            arr[top2].sw=1;
            top2++; arr[top2].x=x; arr[top2].y=(x+y)/2; arr[top2].k=k*2; arr[top2].sw=0;
        }
        else if(arr[top2].sw==1)
        {
            arr[top2].sw=2;
            top2++; arr[top2].x=(x+y)/2+1; arr[top2].y=y; arr[top2].k=k*2+1; arr[top2].sw=0;
        }
        else top2--;
    }
    return maxi;
}
void check()
{
    int i;
    //1
    for(i=1;i<=n;i++){
        if(dap[i]==1) update(s[i],e[i]);
    }
    for(i=1;i<=n;i++){
        if(dap[i]==1 && query(1,t,1,s[i]+1,e[i]-1)>e[i]){printf("IMPOSSIBLE"); exit(0);}
    }
    memset(tree,0,sizeof tree);
    //0
    for(i=1;i<=n;i++){
        if(dap[i]==0) update(s[i],e[i]);
    }
    for(i=1;i<=n;i++){
        if(dap[i]==0 && query(1,t,1,s[i]+1,e[i]-1)>e[i]){printf("IMPOSSIBLE"); exit(0);}
    }
}
int main()
{
    int i;
    scanf("%d",&n);
    for(i=1;i<=n*2;i++)
    {
        scanf("%d",&a[i]);
        if(s[a[i]]==0) s[a[i]]=i;
        else e[a[i]]=i;
    }
    for(i=1;;i++){if(t>=n*2) break; t*=2;}
    for(i=1;i<=t*2;i++) treef[i]=2147483647;
    for(i=1;i<=n;i++)
    {
        updatef(e[i],s[i]);
        updateb(s[i],e[i]);
    }
    for(i=1;i<=n;i++)
    {
        if(ch[i]==0)
        {
            ch[i]=1;
            dap[i]=1;
            q[++r]=i;
            updatef(e[i],2147483647);
            updateb(s[i],0);
            while(f!=r)
            {
                f++;
                for(;;)
                {
                    p=queryf(1,t,1,s[q[f]]+1,e[q[f]]-1);
                    if(p>=s[q[f]]) break;
                    updatef(e[a[p]],2147483647);
                    dap[a[p]]=(dap[q[f]]+1)%2;
                    ch[a[p]]=1;
                    q[++r]=a[p];
                }
                for(;;)
                {
                    p=queryb(1,t,1,s[q[f]]+1,e[q[f]]-1);
                    if(p<=e[q[f]]) break;
                    updateb(s[a[p]],0);
                    dap[a[p]]=(dap[q[f]]+1)%2;
                    ch[a[p]]=1;
                    q[++r]=a[p];
                }
            }
        }
    }
    check();
    for(i=1;i<=n*2;i++)
    {
        if(dap[a[i]]==0) printf("v");
        else printf("^");
    }
    return 0;
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	51876 KB	Output is correct
2	Correct	0 ms	51876 KB	Output is correct
3	Correct	0 ms	51876 KB	Output is correct
4	Correct	0 ms	51876 KB	Output is correct
5	Correct	0 ms	51876 KB	Output is correct
6	Correct	0 ms	51876 KB	Output is correct
7	Correct	0 ms	51876 KB	Output is correct
8	Correct	0 ms	51876 KB	Output is correct
9	Correct	0 ms	51876 KB	Output is correct
10	Correct	0 ms	51876 KB	Output is correct
11	Correct	0 ms	51876 KB	Output is correct
12	Correct	0 ms	51876 KB	Output is correct
13	Correct	0 ms	51876 KB	Output is correct
14	Correct	0 ms	51876 KB	Output is correct
15	Correct	0 ms	51876 KB	Output is correct
16	Correct	0 ms	51876 KB	Output is correct
17	Correct	0 ms	51876 KB	Output is correct
18	Correct	0 ms	51876 KB	Output is correct
19	Correct	0 ms	51876 KB	Output is correct
20	Correct	0 ms	51876 KB	Output is correct
21	Correct	4 ms	51876 KB	Output is correct
22	Correct	0 ms	51876 KB	Output is correct
23	Correct	4 ms	51876 KB	Output is correct
24	Correct	0 ms	51876 KB	Output is correct
25	Correct	0 ms	51876 KB	Output is correct
26	Correct	0 ms	51876 KB	Output is correct
27	Correct	0 ms	51876 KB	Output is correct
28	Correct	0 ms	51876 KB	Output is correct
29	Correct	0 ms	51876 KB	Output is correct
30	Correct	0 ms	51876 KB	Output is correct
31	Correct	0 ms	51876 KB	Output is correct
32	Correct	0 ms	51876 KB	Output is correct
33	Correct	0 ms	51876 KB	Output is correct
34	Correct	0 ms	51876 KB	Output is correct
35	Correct	4 ms	51876 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	51876 KB	Output is correct
2	Correct	0 ms	51876 KB	Output is correct
3	Correct	0 ms	51876 KB	Output is correct
4	Correct	0 ms	51876 KB	Output is correct
5	Correct	0 ms	51876 KB	Output is correct
6	Correct	0 ms	51876 KB	Output is correct
7	Correct	0 ms	51876 KB	Output is correct
8	Correct	0 ms	51876 KB	Output is correct
9	Correct	0 ms	51876 KB	Output is correct
10	Correct	0 ms	51876 KB	Output is correct
11	Correct	0 ms	51876 KB	Output is correct
12	Correct	4 ms	51876 KB	Output is correct
13	Correct	0 ms	51876 KB	Output is correct
14	Correct	0 ms	51876 KB	Output is correct
15	Correct	4 ms	51876 KB	Output is correct
16	Correct	0 ms	51876 KB	Output is correct
17	Correct	4 ms	51876 KB	Output is correct
18	Correct	4 ms	51876 KB	Output is correct
19	Correct	0 ms	51876 KB	Output is correct
20	Correct	0 ms	51876 KB	Output is correct
21	Correct	0 ms	51876 KB	Output is correct
22	Correct	0 ms	51876 KB	Output is correct

Subtask #3
37.0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	51876 KB	Output is correct
2	Correct	28 ms	51876 KB	Output is correct
3	Correct	248 ms	51876 KB	Output is correct
4	Correct	192 ms	51876 KB	Output is correct
5	Correct	152 ms	51876 KB	Output is correct
6	Correct	140 ms	51876 KB	Output is correct
7	Correct	188 ms	51876 KB	Output is correct
8	Correct	8 ms	51876 KB	Output is correct
9	Correct	24 ms	51876 KB	Output is correct
10	Correct	192 ms	51876 KB	Output is correct
11	Correct	120 ms	51876 KB	Output is correct
12	Correct	160 ms	51876 KB	Output is correct
13	Correct	132 ms	51876 KB	Output is correct
14	Correct	176 ms	51876 KB	Output is correct
15	Correct	196 ms	51876 KB	Output is correct
16	Correct	36 ms	51876 KB	Output is correct
17	Correct	40 ms	51876 KB	Output is correct
18	Correct	252 ms	51876 KB	Output is correct
19	Correct	128 ms	51876 KB	Output is correct
20	Correct	220 ms	51876 KB	Output is correct
21	Correct	212 ms	51876 KB	Output is correct
22	Correct	232 ms	51876 KB	Output is correct
23	Correct	252 ms	51876 KB	Output is correct
24	Correct	268 ms	51876 KB	Output is correct
25	Correct	280 ms	51876 KB	Output is correct
26	Correct	200 ms	51876 KB	Output is correct
27	Correct	432 ms	51876 KB	Output is correct
28	Correct	436 ms	51876 KB	Output is correct
29	Correct	368 ms	51876 KB	Output is correct
30	Correct	372 ms	51876 KB	Output is correct

Subtask #4
0.0 / 39.0

#	결과	실행 시간	메모리	Grader output
1	Correct	344 ms	51876 KB	Output is correct
2	Correct	684 ms	51876 KB	Output is correct
3	Correct	400 ms	51876 KB	Output is correct
4	Correct	644 ms	51876 KB	Output is correct
5	Correct	692 ms	51876 KB	Output is correct
6	Correct	840 ms	51876 KB	Output is correct
7	Execution timed out	1000 ms	51876 KB	Program timed out
8	Halted	0 ms	0 KB	-

답안 #12762

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