Submission #72254

#	Time	Username	Problem	Language	Result	Execution time	Memory
72254		cat > /dev/null (#118)	Hill Reconstruction (FXCUP3_hill)	C++17	100 / 100	665 ms	6156 KiB

hill

#include <cstdio>
#include <queue>
#define N 300010

using namespace std;

int n;
long long c;
int x[N], y[N];
int b[N];
bool v[N];

struct st
{
    int i;
    bool operator<(const st &hs) const
    {
        long long lv = 1LL*(y[i]-y[b[i]])*(x[hs.i]-x[b[hs.i]]);
        long long rv = 1LL*(y[hs.i]-y[b[hs.i]])*(x[i]-x[b[i]]);
        return lv==rv? i>hs.i : lv<rv;
    }
};
priority_queue<st> q;

int gcd(int a, int b)
{
    while(a%b)
    {
        int tmp = a%b;
        a = b;
        b = tmp;
    }
    return b;
}

void print(int dx, int dy)
{
    int g = gcd(dx, dy);
    dx /= g;
    dy /= g;
    printf("%d/%d", dy, dx);
}

long long abs(long long val)
{
    return val>0? val : -val;
}

long long area(int i, int j, int k)
{
    return abs(1LL*x[i]*(y[j]-y[k]) + 1LL*x[j]*(y[k]-y[i]) + 1LL*x[k]*(y[i]-y[j]));
}

int main()
{
    scanf("%d %lld", &n, &c);
    for(int i=0; i<n; ++i)
        scanf("%d", x+i);
    for(int i=0; i<n; ++i)
        scanf("%d", y+i);
    c *= 2;
    
    for(int i=1; i<n; ++i)
    {
        b[i] = i-1;
        q.push({i});
    }
    
    while(!q.empty())
    {
        int now = q.top().i;
        q.pop();
        
        if(v[now])
            continue;
        if(b[now] == 0)
        {
            print(x[now]-x[0], y[now]-y[0]);
            break;
        }
        
        long long a = area(now, b[now], b[b[now]]);
        if(a > c)
        {
            print(x[now]-x[b[now]], y[now]-y[b[now]]);
            break;
        }
        c -= a;
        v[b[now]] = true;
        b[now] = b[b[now]];
        q.push({now});
    }
    
    return 0;
}

Compilation message (stderr)

hill.cpp: In function 'int main()':
hill.cpp:56: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:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", x+i);
         ~~~~~^~~~~~~~~~~
hill.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", y+i);
         ~~~~~^~~~~~~~~~~

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