oj.uz

Submission #72277

# Submission time Handle Problem Language Result Execution time Memory
72277 2018-08-26T06:42:30 Z 신딩없는 신딩팀(#2212, willi19, andy627, maruii) Hill Reconstruction (FXCUP3_hill) C++17
32 / 100
 642 ms 37496 KB 
#include <stdio.h>
#include <queue>
#include <set>
#include <algorithm>
#define LL long long
#define pll pair<LL,LL>
#define x first
#define y second
using namespace std;

pll cor[333333];

struct tani{
    LL idx1,idx2;

    bool operator<(const tani A)const{
        return (cor[idx2].y-cor[idx1].y)*(cor[A.idx2].x-cor[A.idx1].x)>(cor[A.idx2].y-cor[A.idx1].y)*(cor[idx2].x-cor[idx1].x);
    }
};

set<tani> stt;
set<LL> sti;

LL gcd(LL x,LL y){
    return y?gcd(y,x%y):x;
}

LL tri(LL i,LL j,LL k){
    return abs(cor[i].x*cor[j].y+cor[j].x*cor[k].y+cor[k].x*cor[i].y-cor[j].x*cor[i].y-cor[k].x*cor[j].y-cor[i].x*cor[k].y);
}

int main(){
    LL n,c;

    scanf("%lld %lld",&n,&c); c<<=1;
    for(LL i=1;i<=n;i++) scanf("%lld",&cor[i].x);
    for(LL i=1;i<=n;i++) scanf("%lld",&cor[i].y);

    for(LL i=1;i<n;i++) stt.insert({i,i+1});
    for(LL i=1;i<=n;i++) sti.insert(i);

    while(1){
        LL idx1=(stt.begin())->idx1;
        LL idx2=(stt.begin())->idx2;
        set<LL>::iterator it=sti.find(idx1);

//        printf("%d %d %lld\n",idx1,idx2,c);

        if(it==sti.begin()){
            LL g=gcd(cor[idx2].y-cor[idx1].y,cor[idx2].x-cor[idx1].x);
            printf("%lld/%lld",(cor[idx2].y-cor[idx1].y)/g,(cor[idx2].x-cor[idx1].x)/g);
            return 0;
        }

        LL idx0=*(--it);
        LL siz=tri(idx0,idx1,idx2);

//        printf("%d %d %d %lld %lld\n",idx0,idx1,idx2,c,siz);

        if(c>=siz) c-=siz;
        else{
            LL g=gcd(cor[idx2].y-cor[idx1].y,cor[idx2].x-cor[idx1].x);
            printf("%lld/%lld",(cor[idx2].y-cor[idx1].y)/g,(cor[idx2].x-cor[idx1].x)/g);
            return 0;
        }

        stt.erase({idx0,idx1}); stt.erase({idx1,idx2}); sti.erase(idx1);
        stt.insert({idx0,idx2});
    }

    return 0;
}

Compilation message

hill.cpp: In function 'int main()':
hill.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld",&n,&c); c<<=1;
     ~~~~~^~~~~~~~~~~~~~~~~~~
hill.cpp:36:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(LL i=1;i<=n;i++) scanf("%lld",&cor[i].x);
                          ~~~~~^~~~~~~~~~~~~~~~~~
hill.cpp:37:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(LL i=1;i<=n;i++) scanf("%lld",&cor[i].y);
                          ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 3 ms 488 KB Output is correct
5 Correct 4 ms 544 KB Output is correct
6 Correct 4 ms 816 KB Output is correct
7 Correct 3 ms 816 KB Output is correct
8 Correct 4 ms 816 KB Output is correct

Subtask #2
0 / 68.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 3 ms 488 KB Output is correct
5 Correct 4 ms 544 KB Output is correct
6 Correct 4 ms 816 KB Output is correct
7 Correct 3 ms 816 KB Output is correct
8 Correct 4 ms 816 KB Output is correct
9 Incorrect 642 ms 37496 KB Output isn't correct
10 Halted 0 ms 0 KB -