oj.uz

답안 #149092

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
149092 2019-09-01T05:44:01 Z USA1(#3634, ecnerwala, scott_wu, ksun48) 최적의 팀 구성 (FXCUP4_squad) C++17
100 / 100
 2332 ms 166600 KB 
#include "squad.h"

#include<bits/stdc++.h>
using namespace std;

using ll = long long;

const int S = 1 << 19;
vector<pair<int, int>> segs[2*S];

ll area(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
	return (ll(b.first) - ll(a.first)) * (ll(c.second) - ll(a.second)) - (ll(c.first) - ll(a.first)) * (ll(b.second) - ll(a.second));
}

void updateHull(vector<pair<int, int>>& hull, pair<int, int> p) {
	assert(hull.empty() || p >= hull.back());
	while (!hull.empty() && hull.back().second <= p.second) {
		hull.pop_back();
	}
	if (!hull.empty()) {
		assert(hull.back() <= p);
		assert(hull.back().second > p.second);
		assert(hull.back().first < p.first);
	}

	while (hull.size() >= 2 && area(hull[hull.size()-2], hull.back(), p) >= 0) {
		hull.pop_back();
	}

	hull.push_back(p);
}

bool compareAngle(pair<int, int> a, pair<int, int> b) {
	return 1ll * a.first * b.second < 1ll * a.second * b.first;
}

vector<pair<int, int>> hull;

void Init(vector<int> A, vector<int> D, vector<int> P){
	int N = int(A.size());

	vector<int> inds(N); iota(inds.begin(), inds.end(), 0);
	// defend on the left, attack on the right
	sort(inds.begin(), inds.end(), [&](int i, int j) { return A[i] - D[i] < A[j] - D[j]; });

	vector<pair<pair<int, int>, int>> evts[2];
	for (int z = 0; z < N; z++) {
		//cerr << z << ' ' << D[inds[z]] << ' ' << A[inds[z]] << ' ' << P[inds[z]] << '\n';
		evts[0].emplace_back(pair<int, int>(D[inds[z]], P[inds[z]]), z);
		evts[1].emplace_back(pair<int, int>(A[inds[z]], P[inds[z]]), z);
	}

	for (int z = 0; z < 2; z++) {
		sort(evts[z].begin(), evts[z].end());
		for (auto it : evts[z]) {
			pair<int, int> p = it.first;
			int i = it.second;
			for (int a = S+i; a > 1; a /= 2) {
				if ((a & 1) == z) {
					// insert p into segs[a]
					updateHull(segs[a], p);
				}
			}
		}
	}

	vector<pair<int, int>> pts;
	for (int a = S-1; a; segs[2*a] = {}, segs[2*a+1] = {}, a--) {
		auto& l = segs[2*a];
		auto& r = segs[2*a+1];
		if (l.empty() || r.empty()) continue;
		//cerr << "a " << a << '\n';
		//cerr << "L" << '\n';
		//for (auto p : l) cerr << p.first << ' ' << p.second << '\n';
		//cerr << "R" << '\n';
		//for (auto p : r) cerr << p.first << ' ' << p.second << '\n';

		for (int i = 0, j = 0; true; ) {
			pts.emplace_back(l[i].first + r[j].first, l[i].second + r[j].second);
			//cerr << l[i].first << ' ' << l[i].second << ' ' << r[j].first << ' ' << r[j].second << ' ' << pts.back().first << ' ' << pts.back().second << '\n';

			if (i+1 < int(l.size()) && j+1 < int(r.size())) {
				if (compareAngle(
							pair<int, int>(l[i].second - l[i+1].second, l[i+1].first - l[i].first),
							pair<int, int>(r[j].second - r[j+1].second, r[j+1].first - r[j].first)
						)){
					i++;
				} else {
					j++;
				}
			} else if (j+1 < int(r.size())) {
				j++;
			} else if (i+1 < int(l.size())) {
				i++;
			} else {
				break;
			}
		}
	}

	sort(pts.begin(), pts.end());
	for (auto it : pts) updateHull(hull, it);

	//for (auto it : hull) { cerr << it.first << ' ' << it.second << '\n'; }
}

long long BestSquad(int X, int Y){
	int mi = -1, ma = int(hull.size())-1;
	auto eval = [&](int i) -> long long {
		return 1ll * hull[i].first * X + 1ll * hull[i].second * Y;
	};
	while (ma - mi > 1) {
		int md = (mi + ma) / 2;
		if (eval(md) <= eval(md+1)) {
			mi = md;
		} else {
			ma = md;
		}
	}
	return eval(ma);
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 24960 KB Output is correct
2 Correct 30 ms 25216 KB Output is correct
3 Correct 1136 ms 73152 KB Output is correct
4 Correct 1084 ms 73224 KB Output is correct
5 Correct 98 ms 34088 KB Output is correct
6 Correct 1858 ms 166596 KB Output is correct
7 Correct 1849 ms 166596 KB Output is correct
8 Correct 1931 ms 166600 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 25056 KB Output is correct
2 Correct 33 ms 25344 KB Output is correct
3 Correct 863 ms 67460 KB Output is correct
4 Correct 877 ms 67588 KB Output is correct
5 Correct 62 ms 28144 KB Output is correct
6 Correct 1016 ms 113400 KB Output is correct
7 Correct 1028 ms 113532 KB Output is correct
8 Correct 1052 ms 113560 KB Output is correct

Subtask #3
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 24960 KB Output is correct
2 Correct 30 ms 25216 KB Output is correct
3 Correct 1136 ms 73152 KB Output is correct
4 Correct 1084 ms 73224 KB Output is correct
5 Correct 98 ms 34088 KB Output is correct
6 Correct 1858 ms 166596 KB Output is correct
7 Correct 1849 ms 166596 KB Output is correct
8 Correct 1931 ms 166600 KB Output is correct
9 Correct 28 ms 25056 KB Output is correct
10 Correct 33 ms 25344 KB Output is correct
11 Correct 863 ms 67460 KB Output is correct
12 Correct 877 ms 67588 KB Output is correct
13 Correct 62 ms 28144 KB Output is correct
14 Correct 1016 ms 113400 KB Output is correct
15 Correct 1028 ms 113532 KB Output is correct
16 Correct 1052 ms 113560 KB Output is correct
17 Correct 102 ms 27512 KB Output is correct
18 Correct 37 ms 25592 KB Output is correct
19 Correct 1222 ms 72968 KB Output is correct
20 Correct 1082 ms 73224 KB Output is correct
21 Correct 81 ms 30448 KB Output is correct
22 Correct 2215 ms 166596 KB Output is correct
23 Correct 2274 ms 166600 KB Output is correct
24 Correct 2332 ms 166596 KB Output is correct