Submission #72248

#	Time	Username	Problem	Language	Result	Execution time	Memory
72248		이시대의진정한망겜스타투 (#118)	Hill Reconstruction (FXCUP3_hill)	C++17	100 / 100	431 ms	28240 KiB

hill

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ldouble;

int N;
pll p[300030];
ll C;
pll operator-(pll a, pll b) { return pll(a.Fi - b.Fi, a.Se - b.Se); }
pll operator+(pll a, pll b) { return pll(a.Fi + b.Fi, a.Se + b.Se); }
ll operator/(pll a, pll b) { return a.Fi * b.Se - a.Se * b.Fi; }
int nxt[600030], pre[600030];
pll data2[600060];
int chk[600060];

ll gc(ll x, ll y) { return y == 0 ? x : gc(y, x%y); }

void upd(pll &a, pll b) {
	if(a.Se * b.Fi < b.Se * a.Fi) a = b;
}

struct str {
	str(){}
	str(ll dx, ll dy) { p = pll(dx, dy); }
	str(pll p) : p(p) {}
	pll p;
	bool operator<(const str &rhs) const {
		return p.Se * rhs.p.Fi < p.Fi * rhs.p.Se;
	}
};

void output(pll p) {
	ll g = gc(p.Fi, p.Se);
	p.Fi /= g;
	p.Se /= g;
	printf("%lld/%lld\n", p.Se, p.Fi);
}

int main() {
	scanf("%d", &N);
	scanf("%lld", &C);
	C *= 2;
	for(int i=1;i<=N;i++) {
		scanf("%lld", &p[i].Fi);
	}
	for(int i=1;i<=N;i++) {
		scanf("%lld", &p[i].Se);
	}
	
	for(int i=1;i<N;i++) data2[i] = p[i+1] - p[i];
	for(int i=0;i<=N;i++) {
		nxt[i] = i + 1;
		pre[i] = i - 1;
	}
	priority_queue <pair<str, int> > pq;
	for(int i=2;i<=N;i++) {
		pq.push(make_pair(str(p[i] - p[i-1]), i - 1));
	}
	int cs = N;
	pll ans = pll(0, 1);
	while(!pq.empty()) {
		auto pr = pq.top(); pq.pop();
		if(chk[pr.Se] == 1) continue;
		if(pre[pr.Se] == 0 || szz(pq) == 0) { output(pr.Fi.p); return 0; }
		pll me = pr.Fi.p;
		if(ans.Se * me.Fi > ans.Fi * me.Se) ans = me;
		pll prp = data2[pre[pr.Se]];
		ll val = prp / (prp + me);
		if(C < val) { output(pr.Fi.p); return 0; }
		C -= val;
		int u = pr.Se, v = pre[u];
		chk[u] = chk[v] = 1;
		int nw = ++cs;
		pre[nw] = pre[v];
		nxt[nw] = nxt[u];
		pre[nxt[u]] = nw;
		nxt[pre[v]] = nw;
		data2[nw] = prp + me;
		pq.push(make_pair(data2[nw], nw));
	}
	output(ans);
	return 0;
}

Compilation message (stderr)

hill.cpp: In function 'int main()':
hill.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
hill.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &C);
  ~~~~~^~~~~~~~~~~~
hill.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &p[i].Fi);
   ~~~~~^~~~~~~~~~~~~~~~~~
hill.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &p[i].Se);
   ~~~~~^~~~~~~~~~~~~~~~~~

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