oj.uz

답안 #154785

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
154785 2019-09-24T15:43:00 Z kostia244 최적의 팀 구성 (FXCUP4_squad) C++17
47 / 100
 2910 ms 124852 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 376 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Correct 1301 ms 30200 KB Output is correct
4 Correct 1297 ms 30116 KB Output is correct
5 Correct 149 ms 7812 KB Output is correct
6 Correct 2582 ms 117964 KB Output is correct
7 Correct 2556 ms 116692 KB Output is correct
8 Correct 2569 ms 117484 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 13 ms 632 KB Output is correct
3 Correct 1302 ms 27896 KB Output is correct
4 Correct 1292 ms 27988 KB Output is correct
5 Correct 89 ms 3960 KB Output is correct
6 Correct 2503 ms 84108 KB Output is correct
7 Correct 2497 ms 84508 KB Output is correct
8 Correct 2511 ms 83560 KB Output is correct

Subtask #3
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Correct 1301 ms 30200 KB Output is correct
4 Correct 1297 ms 30116 KB Output is correct
5 Correct 149 ms 7812 KB Output is correct
6 Correct 2582 ms 117964 KB Output is correct
7 Correct 2556 ms 116692 KB Output is correct
8 Correct 2569 ms 117484 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 13 ms 632 KB Output is correct
11 Correct 1302 ms 27896 KB Output is correct
12 Correct 1292 ms 27988 KB Output is correct
13 Correct 89 ms 3960 KB Output is correct
14 Correct 2503 ms 84108 KB Output is correct
15 Correct 2497 ms 84508 KB Output is correct
16 Correct 2511 ms 83560 KB Output is correct
17 Correct 78 ms 5352 KB Output is correct
18 Correct 17 ms 760 KB Output is correct
19 Correct 1491 ms 30244 KB Output is correct
20 Correct 1490 ms 30260 KB Output is correct
21 Correct 109 ms 5324 KB Output is correct
22 Correct 2870 ms 121160 KB Output is correct
23 Incorrect 2910 ms 124852 KB Output isn't correct
24 Halted 0 ms 0 KB -