oj.uz

Submission #128101

# Submission time Handle Problem Language Result Execution time Memory
128101 2019-07-10T12:23:56 Z yuree5 None (KOI17_cut) C++14
35 / 100
 1000 ms 17556 KB 
#include <cstdio>

int n,cnt;
int vt[1000010],vtt[1000010];
struct xy{
    int x,y;
};
xy B[1000010];
struct se{
    int s,e;
};
int c;
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);
}
bool re(int a){
    int j=a+1;
    vt[a]=1;
   // printf("%d: (%d %d)\n",a,C[a].s,C[a].e);
    bool chk=true;
    while(C[a].e>C[j].e&&C[a].s<C[j].s&&j<c){
     //   printf("%d %d %d %d\n",C[a].s,C[j].s,C[j].e,C[a].e);
        if(vt[j]==0){vt[j]=1;vtt[j]=1;re(j);}
        j++;
        chk=false;
    }   // printf("    (%d  %d) %d\n",a,chk,i);
    if(chk==1){cnt++; return 0;}
    else return 1;
}
int main(){
   // freopen("input.txt","r",stdin);
    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;
    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,ccnt=0;
    //printf("\n\n");
    for(i=0;i<c;i++){
        if(vt[i]==0){re(i);vt[i]=1;}
    }
    for(i=0;i<c;i++){
        if(vtt[i]==0)ccnt++;
    }
    printf("%d %d",ccnt,cnt);
}

Compilation message

cut.cpp: In function 'int main()':
cut.cpp:65:11: warning: unused variable 'e' [-Wunused-variable]
     int s,e,v=0;
           ^
cut.cpp:92:9: warning: unused variable 'j' [-Wunused-variable]
     int j,ccnt=0;
         ^
cut.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
cut.cpp:53: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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 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 376 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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 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 376 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 2 ms 376 KB Output is correct
19 Correct 8 ms 504 KB Output is correct
20 Correct 5 ms 504 KB Output is correct
21 Correct 5 ms 504 KB Output is correct
22 Correct 11 ms 520 KB Output is correct
23 Correct 5 ms 504 KB Output is correct
24 Correct 5 ms 504 KB Output is correct
25 Correct 5 ms 508 KB Output is correct
26 Correct 5 ms 504 KB Output is correct
27 Correct 7 ms 504 KB Output is correct
28 Correct 7 ms 504 KB Output is correct
29 Correct 7 ms 504 KB Output is correct
30 Correct 7 ms 504 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 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 376 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 2 ms 376 KB Output is correct
19 Correct 8 ms 504 KB Output is correct
20 Correct 5 ms 504 KB Output is correct
21 Correct 5 ms 504 KB Output is correct
22 Correct 11 ms 520 KB Output is correct
23 Correct 5 ms 504 KB Output is correct
24 Correct 5 ms 504 KB Output is correct
25 Correct 5 ms 508 KB Output is correct
26 Correct 5 ms 504 KB Output is correct
27 Correct 7 ms 504 KB Output is correct
28 Correct 7 ms 504 KB Output is correct
29 Correct 7 ms 504 KB Output is correct
30 Correct 7 ms 504 KB Output is correct
31 Correct 65 ms 3064 KB Output is correct
32 Execution timed out 1085 ms 17556 KB Time limit exceeded
33 Halted 0 ms 0 KB -