oj.uz

답안 #152470

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
152470 2019-09-08T05:00:13 Z Mahotsukai 최적의 팀 구성 (FXCUP4_squad) C++17
47 / 100
 2900 ms 124432 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;
	}
};
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 p.x * q.y + q.x * r.y + r.x * p.y - p.y * q.x - q.y * r.x - r.y * p.x;
}
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:99:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < arr.size(); i ++){
                  ~~^~~~~~~~~~~~
squad.cpp:100: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:143:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    if(p.x > 0 || !p.x && p.y >= 0) typep = 0;
                  ~~~~~^~~~~~~~~~~
squad.cpp:144: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:163: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:195:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1;
           ~~^~~
squad.cpp:198: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 1297 ms 30200 KB Output is correct
4 Correct 1290 ms 30072 KB Output is correct
5 Correct 149 ms 7840 KB Output is correct
6 Correct 2604 ms 117756 KB Output is correct
7 Correct 2602 ms 116748 KB Output is correct
8 Correct 2579 ms 117492 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 13 ms 632 KB Output is correct
3 Correct 1292 ms 27952 KB Output is correct
4 Correct 1277 ms 28024 KB Output is correct
5 Correct 88 ms 3960 KB Output is correct
6 Correct 2510 ms 83900 KB Output is correct
7 Correct 2505 ms 84604 KB Output is correct
8 Correct 2526 ms 83600 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 1297 ms 30200 KB Output is correct
4 Correct 1290 ms 30072 KB Output is correct
5 Correct 149 ms 7840 KB Output is correct
6 Correct 2604 ms 117756 KB Output is correct
7 Correct 2602 ms 116748 KB Output is correct
8 Correct 2579 ms 117492 KB Output is correct
9 Correct 2 ms 252 KB Output is correct
10 Correct 13 ms 632 KB Output is correct
11 Correct 1292 ms 27952 KB Output is correct
12 Correct 1277 ms 28024 KB Output is correct
13 Correct 88 ms 3960 KB Output is correct
14 Correct 2510 ms 83900 KB Output is correct
15 Correct 2505 ms 84604 KB Output is correct
16 Correct 2526 ms 83600 KB Output is correct
17 Correct 74 ms 5368 KB Output is correct
18 Correct 17 ms 760 KB Output is correct
19 Correct 1490 ms 30244 KB Output is correct
20 Correct 1482 ms 30252 KB Output is correct
21 Correct 110 ms 5332 KB Output is correct
22 Correct 2884 ms 121356 KB Output is correct
23 Incorrect 2900 ms 124432 KB Output isn't correct
24 Halted 0 ms 0 KB -