oj.uz

답안 #72021

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72021 2018-08-26T04:46:29 Z BBBSNG(#2263, youngyojun, sebinkim, dlalswp25) 오르막길 (FXCUP3_hill) C++11
100 / 100
 555 ms 85468 KB 
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
//#define rf(x) (x)=0;while(*p<48)im=*p=='-';while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);if(im)(x)=-(x);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define cb(x) (x)=(!(x))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define INFST (0x7f7f7f7f)
#define INFLLST (0x7f7f7f7f7f7f7f7fll)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ld, ld> pdd;
typedef complex<ld> base;
const ld EPS = (ld)1e-7;
const ld PI = acos(0) * 2;
bool isZero(const ld& x) { return abs(x) <= EPS; }
int sign(const ld& x) { return isZero(x) ? 0 : (0 < x ? 1 : -1); }
ll gcd(ll a, ll b) { for(;b;a%=b,swap(a,b)){} return abs(a); }
pll operator + (const pll& a, const pll& b) { return pll(a.first+b.first, a.second+b.second); }
pll operator - (const pll& a, const pll& b) { return pll(a.first-b.first, a.second-b.second); }
pll operator * (const pll& a, const ll& b) { return pll(a.first*b, a.second*b); }
ll operator * (const pll& a, const pll& b) { return a.first*b.second - b.first*a.second; }
ll ccw(const pll& a, const pll& b, const pll& c) { return a*b + b*c + c*a; }
void fg(vector<int> G[], int a, int b) { G[a].pb(b); G[b].pb(a); }
void fg(vector<pii> G[], int a, int b, int c) { G[a].pb({b, c}); G[b].pb({a, c}); }

const int MAXN = 300005;

inline void answer(ll x, ll y) {
	ll t = gcd(x, y);
	if(t) { x /= t; y /= t; }
	if(!y) x = 1;
	printf("%lld/%lld\n", y, x);
	exit(0);
}

struct NOD {
	NOD() : l(NULL), r(NULL), isDead(false) {}
	NOD *l, *r;
	ll x, y;
	bool isDead;
	
	pll f() { return pll(x, y); }
} *rt;

struct LNE {
	LNE(ll dx, ll dy, NOD *p) : dx(dx), dy(dy), p(p) {}
	ll dx, dy;
	NOD *p;

	bool operator < (const LNE &t) const {
		return dy * t.dx < dx * t.dy;
	}
};

priority_queue<LNE> PQ;

ll X[MAXN], Y[MAXN];

int N; ll C;

int main() {
	ios::sync_with_stdio(false);

	rt = new NOD();
	rt -> isDead = true;

	{
		NOD *p = rt;
		cin >> N >> C; C <<= 1;
		for(int i = 1; i <= N; i++) cin >> X[i];
		for(int i = 1; i <= N; i++) cin >> Y[i];
		for(int i = 1; i <= N; i++) {
			ll x = X[i], y = Y[i];
			NOD *t = new NOD();
			t -> x = x; t -> y = y;
			p -> r = t;
			t -> l = p;
			p = t;
		}
	}

	{
		NOD *p = rt -> r;
		for(;;) {
			if(!(p -> r)) break;
			PQ.push(LNE((p -> r -> x) - (p -> x), (p -> r -> y) - (p -> y), p));
			p = p -> r;
		}
	}

	for(; !PQ.empty() && 0 <= C;) {
		NOD *p = PQ.top().p;
		ll dx = PQ.top().dx, dy = PQ.top().dy;
		PQ.pop();
		if(p -> isDead) continue;
		if(!(p -> r) || p -> r -> isDead) continue;
		if(dx != (p -> r -> x) - (p -> x) || dy != (p -> r -> y) - (p -> y)) continue;
		if(p -> l == rt) answer(dx, dy);
		ll area = abs(ccw(p -> l -> f(), p -> f(), p -> r -> f()));
		if(C < area) answer(dx, dy);
		C -= area;

		p -> r -> l = p -> l;
		p -> l -> r = p -> r;
		dx = (p -> r -> x) - (p -> l -> x);
		dy = (p -> r -> y) - (p -> l -> y);
		p -> isDead = true;
		PQ.push(LNE(dx, dy, p -> l));
	}
	for(; !PQ.empty();) {
		NOD *p = PQ.top().p;
		ll dx = PQ.top().dx, dy = PQ.top().dy;
		PQ.pop();
		if(p -> isDead) continue;
		if(!(p -> r) || p -> r -> isDead) continue;
		if(dx != (p -> r -> x) - (p -> x) || dy != (p -> r -> y) - (p -> y)) continue;
		answer(dx, dy);
	}
	return 0;
}

Subtask #1
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 3 ms 392 KB Output is correct
5 Correct 4 ms 520 KB Output is correct
6 Correct 4 ms 540 KB Output is correct
7 Correct 4 ms 704 KB Output is correct
8 Correct 3 ms 868 KB Output is correct

Subtask #2
68.0 / 68.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 3 ms 392 KB Output is correct
5 Correct 4 ms 520 KB Output is correct
6 Correct 4 ms 540 KB Output is correct
7 Correct 4 ms 704 KB Output is correct
8 Correct 3 ms 868 KB Output is correct
9 Correct 155 ms 37768 KB Output is correct
10 Correct 142 ms 42920 KB Output is correct
11 Correct 555 ms 49180 KB Output is correct
12 Correct 199 ms 55112 KB Output is correct
13 Correct 97 ms 55112 KB Output is correct
14 Correct 91 ms 55112 KB Output is correct
15 Correct 237 ms 66460 KB Output is correct
16 Correct 149 ms 72060 KB Output is correct
17 Correct 146 ms 72060 KB Output is correct
18 Correct 96 ms 72060 KB Output is correct
19 Correct 168 ms 85468 KB Output is correct