Submission #72382

#	Time	Username	Problem	Language	Result	Execution time	Memory
72382		김동현보다 잘함 (#118)	Hill Reconstruction (FXCUP3_hill)	C++17	100 / 100	502 ms	10132 KiB

hill

#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

ll ccw(pll a, pll b, pll c) {
    return a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x;
}

pll arr[300100];
struct str {
    int s, e;
    str(){}
    str(int s, int e):s(s),e(e){}
    bool operator < (const str &A) const {
        return (arr[e].y-arr[s].y)*(arr[A.e].x-arr[A.s].x)<
                (arr[A.e].y-arr[A.s].y)*(arr[e].x-arr[s].x)||
                (((arr[e].y-arr[s].y)*(arr[A.e].x-arr[A.s].x)==
                (arr[A.e].y-arr[A.s].y)*(arr[e].x-arr[s].x))&&s>A.s);
    }
    bool operator == (const str &A) const {
        return s==A.s&&e==A.e;
    }
};

int n;
ll c;
priority_queue<str> pq;
int chk[300100];
int par[300100];
int fin(int a) {
    if (a<=0) return a;
    return par[a] = (chk[a]?a:fin(min(par[a],a-1)));
}

ll gcd(ll a, ll b) {
    if (!a) return b;
    return gcd(b%a,a);
}
void print(str piv) {
    ll a = arr[piv.e].y-arr[piv.s].y, b = arr[piv.e].x-arr[piv.s].x;
    printf("%lld/%lld\n",a/gcd(a,b),b/gcd(a,b));
    exit(0);
}

int main() {
    int i;

    scanf("%d%lld",&n,&c); c*=2;
    for (i=0;i<n;i++) {
        //arr[i].x = (i?arr[i-1].x:0)+rand()%1000;
        scanf("%lld",&arr[i].x);
    }
    for (i=0;i<n;i++) {
        //arr[i].y = (i?arr[i-1].y:0)+rand()%1000;
        scanf("%lld",&arr[i].y);
    }
    for (i=0;i+1<n;i++) pq.push(str(i,i+1));
    for (i=0;i<n;i++) chk[i] = 1;
    for (i=0;i<n;i++) par[i] = i;
    while(!pq.empty()) {
        str piv = pq.top();
        pq.pop();
        if (!chk[piv.s]||!chk[piv.e]) {
            continue;
        }
        if (piv.s==0) print(piv);
        int v = fin(piv.s-1);
        if (c<ccw(arr[v],arr[piv.s],arr[piv.e])) print(piv);
        //printf("%d, %d, %d : %lld\n",v,piv.s,piv.e,ccw(arr[v],arr[piv.s],arr[piv.e]));
        c-=ccw(arr[v],arr[piv.s],arr[piv.e]);
        chk[piv.s] = 0;
        pq.push(str(v,piv.e));
    }

    return 0;
}

Compilation message (stderr)

hill.cpp: In function 'int main()':
hill.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%lld",&n,&c); c*=2;
     ~~~~~^~~~~~~~~~~~~~~~
hill.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&arr[i].x);
         ~~~~~^~~~~~~~~~~~~~~~~~
hill.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&arr[i].y);
         ~~~~~^~~~~~~~~~~~~~~~~~

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