Submission #72227

#	Time	Username	Problem	Language	Result	Execution time	Memory
72227		신딩없는 신딩팀 (#118)	Hill Reconstruction (FXCUP3_hill)	C++17	0 / 100	6 ms	644 KiB

hill

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
struct partion{
    long long p;
    long long q;
};
bool operator<(partion t,partion u)
{
    return t.q*u.p<t.p*u.q;
}
priority_queue<pair<partion,long long > >pq;
long long x[300100];
long long y[300100];
long long s[300100];
long long n,c;
long long n_ind[300100];
long long b_ind[300100];
partion ans;
int main()
{
    scanf("%lld %lld",&n,&c);
    c*=2;
    for(long long i=0;i<n;i++) scanf("%lld",&x[i]);
    for(long long i=0;i<n;i++) scanf("%lld",&y[i]);
    for(long long i=1;i<n;i++) s[i]=s[i-1]+(x[i]-x[i-1])*(y[i]+y[i-1]);
    for(long long i=0;i<n-1;i++)
    {
        partion slope;
        slope.p=x[i+1]-x[i];
        slope.q=y[i+1]-y[i];
        pq.push({slope,i});
        n_ind[i]=i+1;
        b_ind[i]=i-1;
    }
    n_ind[n-1]=n;
    while(1)
    {
        long long ind=pq.top().s;
        ans=pq.top().f;
        //printf("%lld/%lld what\n",ans.q,ans.p);
        //printf("%lld %lld\n",ind,c);
        if(ind==0) break;
        pq.pop();

        long long ind2=n_ind[ind];
        long long ind1=b_ind[ind];

        long long tmp_s=(x[ind2]-x[ind1])*(y[ind2]+y[ind1])-s[ind2]+s[ind1];
        //printf("%lld\n",tmp_s);
        if(tmp_s>c) break;
        for(int i=ind2;i<n;i=n_ind[i]) s[i]+=tmp_s;
        b_ind[ind2]=ind1;
        n_ind[ind1]=ind2;
        partion slope;

        c-=tmp_s;
        slope.p=x[ind2]-x[ind1];
        slope.q=y[ind2]-y[ind1];
        pq.push({slope,ind1});
        }
    //printf("%lld/%lld",ans.q,ans.p);
    long long tmp_q=ans.q;
    long long tmp_p=ans.p;
    long long gcd;
    while(tmp_p>0||tmp_q>0)
    {
        gcd=min(tmp_q,tmp_p);
        if(tmp_q%gcd==0&&tmp_p%gcd==0) break;
        if(tmp_q>tmp_p) tmp_q=tmp_q%tmp_p;
        else tmp_p=tmp_p%tmp_q;
    }
    if(tmp_p==0||tmp_q==0) gcd=max(tmp_p,tmp_q);
    printf("%lld/%lld",ans.q/gcd,ans.p/gcd);

}

Compilation message (stderr)

hill.cpp: In function 'int main()':
hill.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld",&n,&c);
     ~~~~~^~~~~~~~~~~~~~~~~~~
hill.cpp:25:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(long long i=0;i<n;i++) scanf("%lld",&x[i]);
                                ~~~~~^~~~~~~~~~~~~~
hill.cpp:26:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(long long i=0;i<n;i++) scanf("%lld",&y[i]);
                                ~~~~~^~~~~~~~~~~~~~
hill.cpp:75:11: warning: 'gcd' may be used uninitialized in this function [-Wmaybe-uninitialized]
     printf("%lld/%lld",ans.q/gcd,ans.p/gcd);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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