oj.uz

Submission #73199

# Submission time Handle Problem Language Result Execution time Memory
73199 2018-08-28T04:05:43 Z test Hill Reconstruction (FXCUP3_hill) C++14
32 / 100
 1500 ms 35960 KB 
#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);
    }
};
set<frac> st;
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++) {
        st.insert({ 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) {
        frac t = *st.rbegin();
        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;

        st.erase(t);
        st.erase({ cur.first - pre.first, cur.second - pre.second, pre });
        st.insert({ nxt.first - pre.first, nxt.second - pre.second, pre });
    }

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

Compilation message

hill.cpp: In function 'int main()':
hill.cpp:37: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:41: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:44: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.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 476 KB Output is correct
3 Correct 4 ms 476 KB Output is correct
4 Correct 3 ms 616 KB Output is correct
5 Correct 3 ms 704 KB Output is correct
6 Correct 3 ms 704 KB Output is correct
7 Correct 4 ms 704 KB Output is correct
8 Correct 4 ms 868 KB Output is correct

Subtask #2
0 / 68.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 476 KB Output is correct
3 Correct 4 ms 476 KB Output is correct
4 Correct 3 ms 616 KB Output is correct
5 Correct 3 ms 704 KB Output is correct
6 Correct 3 ms 704 KB Output is correct
7 Correct 4 ms 704 KB Output is correct
8 Correct 4 ms 868 KB Output is correct
9 Correct 487 ms 35960 KB Output is correct
10 Correct 432 ms 35960 KB Output is correct
11 Execution timed out 1566 ms 35960 KB Time limit exceeded
12 Halted 0 ms 0 KB -