Submission #72323

#	Time	Username	Problem	Language	Result	Execution time	Memory
72323		신딩없는 신딩팀 (#118)	Hill Reconstruction (FXCUP3_hill)	C++17	32 / 100	1562 ms	146140 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);
    }
};

priority_queue<tani> pq,del;
set<int> st;

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++) pq.push({i,i+1});
    for(int i=1;i<=n;i++) st.insert(i);

    while(1){
        int idx1=pq.top().idx1;
        int idx2=pq.top().idx2;
        set<int>::iterator it=st.find(idx1);

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

        if(it==st.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;
        }

        del.push({idx0,idx1}); del.push({idx1,idx2}); st.erase(idx1);
        while(!pq.empty() && !del.empty()){
            tani top1=pq.top(),top2=del.top();
            if(top1.idx1==top2.idx1 && top1.idx2==top2.idx2) pq.pop(),del.pop();
            else break;
        }
        pq.push({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