답안 #12757 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
12757	2015-01-02T16:51:33 Z	tncks0121	전선 연결하기 (GA9_wire)	C++14	61 / 100	1000 ms	58120 KB

wire

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int n;
int p,t=1,a[600010],ch[600010],top,q[2000010],s[600010],e[600010],dap[1200010],f,r,treeb[3000010],treef[3000010],tree[3000010];
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)
{
    if(s>e) return 2147483647;
    if(s<=x && y<=e) return treef[k];
    if(s>y || e<x) return 2147483647;
    return min(queryf(x,(x+y)/2,k*2,s,e),queryf((x+y)/2+1,y,k*2+1,s,e));
}
int queryb(int x,int y,int k,int s,int e)
{
    if(s>e) return 0;
    if(s<=x && y<=e) return treeb[k];
    if(s>y || e<x) return 0;
    return max(queryb(x,(x+y)/2,k*2,s,e),queryb((x+y)/2+1,y,k*2+1,s,e));
}
int query(int x,int y,int k,int s,int e)
{
    if(s>e) return 0;
    if(s<=x && y<=e) return tree[k];
    if(s>y || e<x) return 0;
    return max(query(x,(x+y)/2,k*2,s,e),query((x+y)/2+1,y,k*2+1,s,e));
}
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++;
                while(queryf(1,t,1,s[q[f]]+1,e[q[f]]-1)<s[q[f]])
                {
                    p=queryf(1,t,1,s[q[f]]+1,e[q[f]]-1);
                    updatef(e[a[p]],2147483647);
                    dap[a[p]]=(dap[q[f]]+1)%2;
                    ch[a[p]]=1;
                    q[++r]=a[p];
                }
                while(queryb(1,t,1,s[q[f]]+1,e[q[f]]-1)>e[q[f]])
                {
                    p=queryb(1,t,1,s[q[f]]+1,e[q[f]]-1);
                    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	58120 KB	Output is correct
2	Correct	0 ms	58120 KB	Output is correct
3	Correct	0 ms	58120 KB	Output is correct
4	Correct	0 ms	58120 KB	Output is correct
5	Correct	0 ms	58120 KB	Output is correct
6	Correct	0 ms	58120 KB	Output is correct
7	Correct	4 ms	58120 KB	Output is correct
8	Correct	0 ms	58120 KB	Output is correct
9	Correct	0 ms	58120 KB	Output is correct
10	Correct	4 ms	58120 KB	Output is correct
11	Correct	0 ms	58120 KB	Output is correct
12	Correct	0 ms	58120 KB	Output is correct
13	Correct	0 ms	58120 KB	Output is correct
14	Correct	0 ms	58120 KB	Output is correct
15	Correct	0 ms	58120 KB	Output is correct
16	Correct	0 ms	58120 KB	Output is correct
17	Correct	0 ms	58120 KB	Output is correct
18	Correct	0 ms	58120 KB	Output is correct
19	Correct	0 ms	58120 KB	Output is correct
20	Correct	4 ms	58120 KB	Output is correct
21	Correct	4 ms	58120 KB	Output is correct
22	Correct	0 ms	58120 KB	Output is correct
23	Correct	0 ms	58120 KB	Output is correct
24	Correct	0 ms	58120 KB	Output is correct
25	Correct	0 ms	58120 KB	Output is correct
26	Correct	0 ms	58120 KB	Output is correct
27	Correct	0 ms	58120 KB	Output is correct
28	Correct	0 ms	58120 KB	Output is correct
29	Correct	0 ms	58120 KB	Output is correct
30	Correct	0 ms	58120 KB	Output is correct
31	Correct	0 ms	58120 KB	Output is correct
32	Correct	0 ms	58120 KB	Output is correct
33	Correct	0 ms	58120 KB	Output is correct
34	Correct	0 ms	58120 KB	Output is correct
35	Correct	0 ms	58120 KB	Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
37.0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	58120 KB	Output is correct
2	Correct	28 ms	58120 KB	Output is correct
3	Correct	200 ms	58120 KB	Output is correct
4	Correct	172 ms	58120 KB	Output is correct
5	Correct	136 ms	58120 KB	Output is correct
6	Correct	116 ms	58120 KB	Output is correct
7	Correct	164 ms	58120 KB	Output is correct
8	Correct	8 ms	58120 KB	Output is correct
9	Correct	24 ms	58120 KB	Output is correct
10	Correct	156 ms	58120 KB	Output is correct
11	Correct	112 ms	58120 KB	Output is correct
12	Correct	132 ms	58120 KB	Output is correct
13	Correct	116 ms	58120 KB	Output is correct
14	Correct	136 ms	58120 KB	Output is correct
15	Correct	172 ms	58120 KB	Output is correct
16	Correct	32 ms	58120 KB	Output is correct
17	Correct	28 ms	58120 KB	Output is correct
18	Correct	208 ms	58120 KB	Output is correct
19	Correct	124 ms	58120 KB	Output is correct
20	Correct	180 ms	58120 KB	Output is correct
21	Correct	184 ms	58120 KB	Output is correct
22	Correct	200 ms	58120 KB	Output is correct
23	Correct	220 ms	58120 KB	Output is correct
24	Correct	240 ms	58120 KB	Output is correct
25	Correct	240 ms	58120 KB	Output is correct
26	Correct	176 ms	58120 KB	Output is correct
27	Correct	356 ms	58120 KB	Output is correct
28	Correct	344 ms	58120 KB	Output is correct
29	Correct	296 ms	58120 KB	Output is correct
30	Correct	312 ms	58120 KB	Output is correct

Subtask #4
0.0 / 39.0

#	결과	실행 시간	메모리	Grader output
1	Correct	316 ms	58120 KB	Output is correct
2	Correct	600 ms	58120 KB	Output is correct
3	Correct	348 ms	58120 KB	Output is correct
4	Correct	564 ms	58120 KB	Output is correct
5	Correct	612 ms	58120 KB	Output is correct
6	Correct	752 ms	58120 KB	Output is correct
7	Correct	936 ms	58120 KB	Output is correct
8	Correct	724 ms	58120 KB	Output is correct
9	Correct	452 ms	58120 KB	Output is correct
10	Correct	348 ms	58120 KB	Output is correct
11	Correct	452 ms	58120 KB	Output is correct
12	Correct	472 ms	58120 KB	Output is correct
13	Correct	920 ms	58120 KB	Output is correct
14	Correct	632 ms	58120 KB	Output is correct
15	Correct	364 ms	58120 KB	Output is correct
16	Correct	412 ms	58120 KB	Output is correct
17	Correct	460 ms	58120 KB	Output is correct
18	Correct	428 ms	58120 KB	Output is correct
19	Correct	656 ms	58120 KB	Output is correct
20	Correct	932 ms	58120 KB	Output is correct
21	Correct	872 ms	58120 KB	Output is correct
22	Execution timed out	1000 ms	58120 KB	Program timed out
23	Halted	0 ms	0 KB	-

답안 #12757

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