Submission #72333

#	Time	Username	Problem	Language	Result	Execution time	Memory
72333		김동현보다 잘함 (#118)	Hill Reconstruction (FXCUP3_hill)	C++17	32 / 100	1541 ms	33472 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;
set<str> pq;
set<int> lis;

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++) scanf("%lld",&arr[i].x);
    for (i=0;i<n;i++) scanf("%lld",&arr[i].y);
    for (i=0;i+1<n;i++) pq.insert(str(i,i+1));
    for (i=0;i<n;i++) lis.insert(i);
    while(!pq.empty()) {
        str piv = *(--pq.end());
        if (piv.s==0) {
            print(piv);
        }
        int v = *(--lis.find(piv.s));
        str pre = *pq.find(str(v,piv.s));
        if (c<ccw(arr[v],arr[piv.s],arr[piv.e])) {
            break;
        }
        //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]);
        pq.erase(piv);
        pq.erase(pre);
        lis.erase(piv.s);
        pq.insert(str(v,piv.e));
    }
    print(*(--pq.end()));

    return 0;
}

Compilation message (stderr)

hill.cpp: In function 'int main()':
hill.cpp:49: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:50:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i=0;i<n;i++) scanf("%lld",&arr[i].x);
                       ~~~~~^~~~~~~~~~~~~~~~~~
hill.cpp:51:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i=0;i<n;i++) scanf("%lld",&arr[i].y);
                       ~~~~~^~~~~~~~~~~~~~~~~~

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