Submission #72263

#	Time	Username	Problem	Language	Result	Execution time	Memory
72263		신딩없는 신딩팀 (#118)	Hill Reconstruction (FXCUP3_hill)	C++17	32 / 100	685 ms	33104 KiB

hill

#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{
    int 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<int> sti;

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

LL tri(int i,int j,int 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(int i=1;i<=n;i++) scanf("%lld",&cor[i].x);
    for(int i=1;i<=n;i++) scanf("%lld",&cor[i].y);

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

    while(1){
        int idx1=(stt.begin())->idx1;
        int idx2=(stt.begin())->idx2;
        set<int>::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;
        }

        int 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 (stderr)

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:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++) scanf("%lld",&cor[i].x);
                           ~~~~~^~~~~~~~~~~~~~~~~~
hill.cpp:37:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++) scanf("%lld",&cor[i].y);
                           ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 32 / 32
• Subtask 2: 0 / 68