oj.uz

답안 #128042

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
128042 2019-07-10T10:54:19 Z yuree5 곡선 자르기 (KOI17_cut) C++14
35 / 100
 1000 ms 26724 KB 
#include <cstdio>

int n;
int vt[1000010];
struct xy{
    int x,y;
};
xy B[1000010];
struct se{
    int s,e;
};
se C[1000010],t[1000010];
void mers(int s,int m,int e){
    int i,p1=s,p2=m+1;
    for(i=s;i<=e;i++){
        if(p1>m||(p2<=e&&C[p1].s>C[p2].s))t[i]=C[p2++];
        else if((p2<=e&&C[p1].s==C[p2].s)){
            if(C[p1].e<C[p2].s)t[i]=C[p2++];
        }
        else t[i]=C[p1++];
    }
    for(i=s;i<=e;i++){
        C[i]=t[i];
    }
}
void msort(int s,int e){
    if(s>=e)return;
    int m=(s+e)/2;
    msort(s,m);
    msort(m+1,e);
    mers(s,m,e);
}
int main(){
    scanf("%d",&n);
    int i,mx=0,my=1000000010,mxi=0;
    for(i=0;i<n;i++){
        scanf("%d %d",&B[i].x,&B[i].y);
        if(B[i].x>mx){
            if(B[i].y<=my){
                mx=B[i].x;
                my=B[i].y;
                mxi=i;
            }
        }else if(B[i].x==mx&&B[i].y<my){
            mx=B[i].x;my=B[i].y;
            mxi=i;
        }
    }
    int s,e,v=0;
    int c=0;
    for(i=mxi;i<n;i++){
        int val=i+1;
        if(val==n)val=0;
        if(B[i].y<0&&B[val].y>0){v=1;s=B[i].x;}
        if(v==1&&B[i].y>0&&B[val].y<0){
            v=0;
            C[c].s=s;
            C[c++].e=B[i].x;
        }
    }
    for(i=0;i<mxi;i++){
        if(B[i].y<0&&B[i+1].y>0){v=1;s=B[i].x;}
        if(v==1&&B[i].y>0&&B[i+1].y<0){
            v=0;
            C[c].s=s;
            C[c++].e=B[i].x;
        }
    }
    for(i=0;i<c;i++){
        if(C[i].e<C[i].s){
            int t=C[i].e;
            C[i].e=C[i].s;
            C[i].s=t;
        }
    }
    msort(0,c-1);
    int j,cnt=0,ccnt=0;
   // printf("\n\n");
    for(i=0;i<c;i++){
        j=i+1;
        bool chk=false;
       // printf("%d :\n",i);
        while(C[i].e>C[j].e&&C[i].s<C[j].s&&j<c){
            //printf("%d %d %d %d\n",C[i].s,C[j].s,C[j].e,C[i].e);
            if(vt[j]==0)cnt++;
            vt[j]=1;
            j++;
            chk=true;
        }
        if(chk==false)ccnt++;
       // printf("\n");
    }
    printf("%d %d",c-cnt,ccnt);
}

Compilation message

cut.cpp: In function 'int main()':
cut.cpp:49:11: warning: unused variable 'e' [-Wunused-variable]
     int s,e,v=0;
           ^
cut.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
cut.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&B[i].x,&B[i].y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct

Subtask #2
24.0 / 24.0

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

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 3 ms 376 KB Output is correct
19 Correct 8 ms 632 KB Output is correct
20 Correct 5 ms 632 KB Output is correct
21 Correct 5 ms 632 KB Output is correct
22 Correct 10 ms 636 KB Output is correct
23 Correct 5 ms 632 KB Output is correct
24 Correct 5 ms 632 KB Output is correct
25 Correct 5 ms 632 KB Output is correct
26 Correct 5 ms 604 KB Output is correct
27 Correct 7 ms 632 KB Output is correct
28 Correct 7 ms 632 KB Output is correct
29 Correct 7 ms 632 KB Output is correct
30 Correct 7 ms 636 KB Output is correct
31 Correct 66 ms 6820 KB Output is correct
32 Execution timed out 1069 ms 26724 KB Time limit exceeded
33 Halted 0 ms 0 KB -