oj.uz

답안 #152631

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
152631 2019-09-08T16:53:07 Z Mahotsukai 최적의 팀 구성 (FXCUP4_squad) C++17
47 / 100
 2863 ms 124724 KB 
#include<bits/stdc++.h>
#include<chrono>
using namespace std;
using namespace chrono;
#define all(a) a.begin(), a.end()
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef vector<string> vs;
template<class T1, class T2>
istream &operator>>(istream &in, pair<T1, T2> &P){
	in >> P.first >> P.second;
	return in;
}
template<class T1, class T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &P){
	out << "(" << P.first << ", " << P.second << ")";
	return out;
}
template<class T>
istream &operator>>(istream &in, vector<T> &arr){
	for(auto &x: arr) in >> x;
	return in;
}
template<class T>
ostream &operator<<(ostream &out, const vector<T> &arr){
	for(auto &x: arr) out << x << ' '; cout << "\n";
	return out;
}
template<class T>
istream &operator>>(istream &in, deque<T> &arr){
	for(auto &x: arr) in >> x;
	return in;
}
template<class T>
ostream &operator<<(ostream &out, const deque<T> &arr){
	for(auto &x: arr) out << x << ' '; cout << "\n";
	return out;
}

struct point{
	ll x, y;
	point(pll p): x(p.first), y(p.second){}
	point(ll x = 0, ll y = 0): x(x), y(y){}
	bool operator<(const point &other) const{
		return x < other.x || (x == other.x && y < other.y);
	}
	point operator+(const point &other) const{
		return point(x + other.x, y + other.y);
	}
	point operator+=(const point &other){
		return *this = *this + other;
	}
	point operator-(const point &other) const{
		return point(x - other.x, y - other.y);
	}
	point operator-=(const point &other){
		return *this = *this - other;
	}
	bool operator==(const point &other) const{
		return x == other.x && y == other.y;
	}
	ll operator*(const point &other) const{
		return x * other.x + y * other.y;
	}
	ll operator^(const point &other) const{
		return x * other.y - y * other.x;
	}
};
istream &operator>>(istream &in, point &p){
	cin >> p.x >> p.y;
	return in;
}
ostream &operator<<(ostream &out, const point &p){
	cout << "(" << p.x << ", " << p.y << ")";
	return out;
}
ll ori(const point &p, const point &q, const point &r){
	return (q - p) ^ (r - p);
}
struct convhull{
	int N, R;
	vector<point> ch;
	convhull(vector<point> arr = vector<point>(), bool sorted = false){
		if(!sorted){
			sort(all(arr));
		}
		arr.resize(unique(all(arr)) - arr.begin());
		if(arr.size() <= 1){
			ch = arr;
			N = R = arr.size();
			if(N) R --;
			return;
		}
		vector<point> upper;
		point p = arr.front(), q = arr.back();
		upper.push_back(p);
		for(int i = 1; i < arr.size(); i ++){
			if(i == arr.size() - 1 || ori(p, arr[i], q) < 0){
				while(upper.size() >= 2 && ori(upper[upper.size() - 2], upper[upper.size() - 1], arr[i]) >= 0){
					upper.pop_back();
				}
				upper.push_back(arr[i]);
			}
		}
		ch.push_back(p), ch.push_back(q);
		for(int i = upper.size() - 2; i; i --) ch.push_back(upper[i]);
		N = ch.size();
		R = 1;
	}
	vector<point> linearize() const{
		if(N <= 1) return ch;
		int i = 0, j = N - 1;
		vector<point> res(N);
		int cnt = 0;
		while(i <= j){
			if(ch[i] < ch[j]) res[cnt ++] = ch[i ++];
			else res[cnt ++] = ch[j --];
		}
		return res;
	}
	int max_element(ll x, ll y){
		point p(x, y);
		int l = R, r = N;
		while(r - l > 3){
			int m1 = (2 * l + r) / 3, m2 = (l + 2 * r) / 3;
			p * ch[m1] <= p * ch[m2] ? l = m1 : r = m2;
		}
		int res = 0;
		for(int i = l; i < r; i ++) if(p * ch[res] < p * ch[i]) res = i;
		return res;
	}
	convhull operator+(const convhull &other) const{
		if(!N || !other.N) return convhull();
		vector<point> temp1(ch), temp2(other.ch);
		for(int i = 0; i + 1 < N; i ++) temp1[i] = ch[i + 1] - ch[i];
		for(int i = 0; i + 1 < other.N; i ++) temp2[i] = other.ch[i + 1] - other.ch[i];
		temp1.back() = ch.front() - ch.back();
		temp2.back() = other.ch.front() - other.ch.back();
		function<bool(point, point)> cmp = [&](point p, point q){
			int typep = 1, typeq = 1;
			if(p.x > 0 || !p.x && p.y >= 0) typep = 0;
			if(q.x > 0 || !q.x && q.y >= 0) typeq = 0;
			if(typep != typeq) return typep < typeq;
			return ori(p, q, point(0, 0)) > 0;
		};
		vector<point> temp(N + other.N);
		int cnt = 0;
		int i = 0, j = 0;
		while(i < N && j < other.N){
			if(cmp(temp1[i], temp2[j])) temp[cnt ++] = temp1[i ++];
			else temp[cnt ++] = temp2[j ++];
		}
		for(; i < N; i ++) temp[cnt ++] = temp1[i ++];
		for(; j < other.N; j ++) temp[cnt ++] = temp2[j ++];
		convhull res;
		res.N = N + other.N;
		res.ch.resize(res.N);
		cnt = 0;
		res.ch[cnt ++] = ch[0] + other.ch[0];
		for(int i = 0; i + 1 < res.N; i ++){
			res.ch[cnt ++] = res.ch[cnt - 1] + temp[i];
		}
		res.R = std::max_element(all(res.ch)) - res.ch.begin();
		return res;
	}
	convhull operator^(const convhull &other) const{
		if(!N) return other;
		if(!other.N) return *this;
		auto temp1 = linearize(), temp2 = other.linearize();
		vector<point> res(temp1.size() + temp2.size());
		merge(all(temp1), all(temp2), res.begin());
		return convhull(res, true);
	}
	convhull operator-() const{
		convhull res(*this);
		res.R = N - R;
		if(N == 1) res.R = 0;
		for(int i = 0; i + R < N; i ++) res.ch[i] = point(-ch[i + R].x, -ch[i + R].y);
		for(int i = N - R; i < N; i ++) res.ch[i] = point(-ch[i + R - N].x, -ch[i + R - N].y);
		return res;
	}
};
convhull c;
typedef tuple<convhull, convhull, convhull> tccc;
void Init(vi a, vi d, vi p){
	int n = a.size();
	vector<vector<point>> data(2, vector<point>(n));
	for(int i = 0; i < n; i ++) data[0][i] = point(a[i], p[i]), data[1][i] = point(d[i], p[i]);
	function<tccc(int, int)> solve = [&](int l, int r){
		if(r - l == 1){
			return tccc(convhull({data[0][l]}), convhull({data[1][l]}), convhull());
		}
		int m = l + r >> 1;
		auto [p1, p2, p3] = solve(l, m);
		auto [q1, q2, q3] = solve(m, r);
		return tccc(p1 ^ q1, p2 ^ q2, p1 + q2 ^ p2 + q1 ^ (p3 ^ q3));
	};
	c = get<2>(solve(0, n));
}
ll BestSquad(int x, int y){
	return point(x, y) * c.ch[c.max_element(x, y)];
}

Compilation message

squad.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::vector<_Tp>&)':
squad.cpp:31:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(auto &x: arr) out << x << ' '; cout << "\n";
  ^~~
squad.cpp:31:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(auto &x: arr) out << x << ' '; cout << "\n";
                                     ^~~~
squad.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::deque<_Tp>&)':
squad.cpp:41:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(auto &x: arr) out << x << ' '; cout << "\n";
  ^~~
squad.cpp:41:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(auto &x: arr) out << x << ' '; cout << "\n";
                                     ^~~~
squad.cpp: In constructor 'convhull::convhull(std::vector<point>, bool)':
squad.cpp:102:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < arr.size(); i ++){
                  ~~^~~~~~~~~~~~
squad.cpp:103:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(i == arr.size() - 1 || ori(p, arr[i], q) < 0){
       ~~^~~~~~~~~~~~~~~~~
squad.cpp: In lambda function:
squad.cpp:146:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    if(p.x > 0 || !p.x && p.y >= 0) typep = 0;
                  ~~~~~^~~~~~~~~~~
squad.cpp:147:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    if(q.x > 0 || !q.x && q.y >= 0) typeq = 0;
                  ~~~~~^~~~~~~~~~~
squad.cpp: In member function 'convhull convhull::operator+(const convhull&) const':
squad.cpp:166:15: warning: operation on 'cnt' may be undefined [-Wsequence-point]
    res.ch[cnt ++] = res.ch[cnt - 1] + temp[i];
           ~~~~^~
squad.cpp: In lambda function:
squad.cpp:198:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1;
           ~~^~~
squad.cpp:201:36: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   return tccc(p1 ^ q1, p2 ^ q2, p1 + q2 ^ p2 + q1 ^ (p3 ^ q3));
                                 ~~~^~~~

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Correct 1304 ms 30140 KB Output is correct
4 Correct 1292 ms 30200 KB Output is correct
5 Correct 148 ms 7960 KB Output is correct
6 Correct 2545 ms 117788 KB Output is correct
7 Correct 2532 ms 116692 KB Output is correct
8 Correct 2560 ms 117540 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 12 ms 632 KB Output is correct
3 Correct 1299 ms 27992 KB Output is correct
4 Correct 1286 ms 27976 KB Output is correct
5 Correct 88 ms 3832 KB Output is correct
6 Correct 2483 ms 84108 KB Output is correct
7 Correct 2520 ms 84556 KB Output is correct
8 Correct 2481 ms 83660 KB Output is correct

Subtask #3
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Correct 1304 ms 30140 KB Output is correct
4 Correct 1292 ms 30200 KB Output is correct
5 Correct 148 ms 7960 KB Output is correct
6 Correct 2545 ms 117788 KB Output is correct
7 Correct 2532 ms 116692 KB Output is correct
8 Correct 2560 ms 117540 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 12 ms 632 KB Output is correct
11 Correct 1299 ms 27992 KB Output is correct
12 Correct 1286 ms 27976 KB Output is correct
13 Correct 88 ms 3832 KB Output is correct
14 Correct 2483 ms 84108 KB Output is correct
15 Correct 2520 ms 84556 KB Output is correct
16 Correct 2481 ms 83660 KB Output is correct
17 Correct 75 ms 5288 KB Output is correct
18 Correct 17 ms 760 KB Output is correct
19 Correct 1479 ms 29344 KB Output is correct
20 Correct 1481 ms 30200 KB Output is correct
21 Correct 108 ms 5312 KB Output is correct
22 Correct 2863 ms 121348 KB Output is correct
23 Incorrect 2851 ms 124724 KB Output isn't correct
24 Halted 0 ms 0 KB -