Submission #73202

#	Time	Username	Problem	Language	Result	Execution time	Memory
73202		test	Hill Reconstruction (FXCUP3_hill)	C++14	100 / 100	1341 ms	46312 KiB

hill

#include<bits/stdc++.h>
using namespace std;

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

const int MN = 300010;

ll cross(pii a, pii b) {
    return 1LL * a.first * b.second - 1LL * a.second * b.first;
}
ll ccw(pii a, pii b, pii c) {
    pii p = pii(b.first - a.first, b.second - a.second);
    pii q = pii(c.first - a.first, c.second - a.second);
    return cross(p, q);
}

int gcd(int a, int b) {
    return b? gcd(b, a % b) : a;
}

int N;
ll C;
pii P[MN];

struct frac {
    int a, b;
    pii p;
    bool operator <(const frac &i) const {
        return 1LL * b * i.a < 1LL * a * i.b || (1LL * b * i.a == 1LL * a * i.b && p < i.p);
    }
};
priority_queue<frac> pq;
map<frac, int> chk;
set<pii> pp;

int main() {
    scanf("%d %lld", &N, &C);
    C *= 2;

    for(int i = 0; i < N; i++) {
        scanf("%d", &P[i].first);
    }
    for(int i = 0; i < N; i++) {
        scanf("%d", &P[i].second);
    }

    for(int i = 0; i < N - 1; i++) {
        pq.push({ P[i + 1].first - P[i].first, P[i + 1].second - P[i].second, P[i] });
    }
    for(int i = 0; i < N; i++) {
        pp.insert(P[i]);
    }

    while(1) {
        while(!pq.empty() && chk[ pq.top() ]) pq.pop();
        frac t = pq.top();
        pii cur = t.p;
        pp.erase(cur);

        set<pii>::iterator it = pp.lower_bound(cur);
        if(it == pp.begin()) break;

        pii nxt = *it;
        pii pre = *(--it);

        ll need = abs(ccw(pre, cur, nxt));
        if(need > C) break;
        C -= need;

        pq.pop();
        chk[ { cur.first - pre.first, cur.second - pre.second, pre } ] = 1;
        pq.push({ nxt.first - pre.first, nxt.second - pre.second, pre });
    }

    frac t = pq.top();
    int A = t.a;
    int B = t.b;
    int G = gcd(A, B);
    A /= G;
    B /= G;
    printf("%d/%d", B, A);
}

Compilation message (stderr)

hill.cpp: In function 'int main()':
hill.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %lld", &N, &C);
     ~~~~~^~~~~~~~~~~~~~~~~~~
hill.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &P[i].first);
         ~~~~~^~~~~~~~~~~~~~~~~~~
hill.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &P[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~

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