oj.uz

Submission #72333

# Submission time Handle Problem Language Result Execution time Memory
72333 2018-08-26T07:12:27 Z 김동현보다 잘함(#2226, tlwpdus) Hill Reconstruction (FXCUP3_hill) C++17
32 / 100
 1500 ms 33472 KB 
#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

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.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 4 ms 480 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 4 ms 676 KB Output is correct
6 Correct 4 ms 676 KB Output is correct
7 Correct 3 ms 676 KB Output is correct
8 Correct 4 ms 676 KB Output is correct

Subtask #2
0 / 68.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 4 ms 480 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 4 ms 676 KB Output is correct
6 Correct 4 ms 676 KB Output is correct
7 Correct 3 ms 676 KB Output is correct
8 Correct 4 ms 676 KB Output is correct
9 Correct 658 ms 33472 KB Output is correct
10 Correct 589 ms 33472 KB Output is correct
11 Execution timed out 1541 ms 33472 KB Time limit exceeded
12 Halted 0 ms 0 KB -