oj.uz

답안 #152366

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
152366 2019-09-07T19:22:04 Z Mahotsukai 최적의 팀 구성 (FXCUP4_squad) C++17
47 / 100
 2981 ms 115440 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;
	}
	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(arr.size() <= 1){
			ch = arr;
			N = R = arr.size();
			if(N) R --;
			return;
		}
		if(!sorted) sort(arr.begin(), arr.end());
		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];
			while(cnt >= 3 && !ori(res.ch[cnt - 1], res.ch[cnt - 2], res.ch[cnt - 3])){
				res.ch[cnt - 2] = res.ch[cnt - 1];
				cnt --;
			}
		}
		res.ch.resize(cnt);
		res.N = cnt;
		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)];
}
/*
12 
6 1 1 
5 1 2 
4 1 3 
3 1 4 
2 1 5
1 1 6
6 1 1 
5 1 2 
4 1 3 
3 1 4 
2 1 5
1 1 6
100 

4 
3 1 4 
2 3 3 
2 1 6 
4 4 1 
2 
1 3 
3 1 

2
1 2 3
1 2 3
2
1 1
3 1
1 3
*/

//////////////////////////////////////////////////////////////////////////////////////////////////////
//                                                                                                  //
//                                                                                                  //
//                                              _____________                                       //
//             ++++++++++                ___------------------\\\\                                  //
//           +++`+``+`+`++++        ///`````````````````````````````\\\                             //
//           ++`+`+``+++`++++  /////```````````````````````````````````\\                           //
//           +++`++`+`+``+++/////`````````````````````````````````````````\\                        //
//             +++`++`+``+///```````````|```````````````````````````````````\\                      //
//          ____++++/++++/`````````````/````````|````````|```````````````````\\                     //
//        /  /  / |    //``````````````|````````|```````|````````|````````````\\                    //
//       /  /  /  | ///````````/```````|```````||```````|````````|``````\```````\\                  //
//       | /  /   |///`````````|``````/````````|````````|````````|```````|```````\\                 //
//       |/   |   |//``|```````|``````|````````|`````````|```````|```````|````````\\                //
//       /\___|__//`|``|```````|`    |      ``:|````````|:```````|```````|```|`````|                //
//      /     /  /``|``|``````|/     |        :|     ```:|```````|```````|``++````++                //
//     /     / //```|``|``````|      |        |:        :|    ```|```````|```++``++`\               //
//     |    /  /````|``|``````/    _.::::.    |          |      |    ````|```|`++`\`|               //
//     |   /   |````|``|`````|            `                    |       ``|```++``++`|               //
//     |  /    |````|``|`````|                                 :         |``++````++|               //
//     | /     /````|``|`````|                              _.-:::.      |..`|``.`|.|               //
//     |/     /`````|``|`````|                                     `     |```|````|`|               //
//    /|      |`````|``|`````|                    :'                    .|```|````|.|               //
//   / |      |`````|``|`````|                                         /|-|``|````|`|               //
//  /  |      |`````|```\````|                                        / ||```|````|``\              //
// /   |      |`````|````|```|::                                    /_| ||```|````|``|              //
//            |`````|````|```|:|:.        `.._                    .\___/:|```|````|``|              //
//            |`````\````|```|:|::-          ``:::....           -:|:|:::|```|````|``|              //
//            |``````|```|```|:|::`|.                          .:::|:|:::|```|````|``|              //
//             \`````|```|```|:|::/|--.                     .`:|:::|:|:::/```|````|``|              //
//              |````|```|```\:|:|:|-----             _..-:|:|:|:::|:|::|````|````|`/               //
//              |````|```|````\|:|:|-------.____.....------|/::|:::|:|::|````|````|`|               //
//              |````|```|\````\:|/\___________    ________/\--\:::|:|::|````/````|`|               //
//              |````\```| \```|:/-------------\  /----------\``\::|:|::|```/`````|`|               //
//              |`````|``|  \``|/---------------\/------------\_________|```|`````|`|               //
//                                                                                                  //
//////////////////////////////////////////////////////////////////////////////////////////////////////
//                                                                                                  //
//                                        Created by Aeren                                          //
//                                                                                                  //
//////////////////////////////////////////////////////////////////////////////////////////////////////

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:93:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < arr.size(); i ++){
                  ~~^~~~~~~~~~~~
squad.cpp:94: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:137:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    if(p.x > 0 || !p.x && p.y >= 0) typep = 0;
                  ~~~~~^~~~~~~~~~~
squad.cpp:138: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:157: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 1275 ms 23072 KB Output is correct
4 Correct 1275 ms 23000 KB Output is correct
5 Correct 154 ms 7868 KB Output is correct
6 Correct 2637 ms 112476 KB Output is correct
7 Correct 2675 ms 107676 KB Output is correct
8 Correct 2655 ms 113244 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 1284 ms 23096 KB Output is correct
4 Correct 1294 ms 23164 KB Output is correct
5 Correct 88 ms 3956 KB Output is correct
6 Correct 2523 ms 76860 KB Output is correct
7 Correct 2479 ms 78404 KB Output is correct
8 Correct 2472 ms 79756 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 1275 ms 23072 KB Output is correct
4 Correct 1275 ms 23000 KB Output is correct
5 Correct 154 ms 7868 KB Output is correct
6 Correct 2637 ms 112476 KB Output is correct
7 Correct 2675 ms 107676 KB Output is correct
8 Correct 2655 ms 113244 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 12 ms 632 KB Output is correct
11 Correct 1284 ms 23096 KB Output is correct
12 Correct 1294 ms 23164 KB Output is correct
13 Correct 88 ms 3956 KB Output is correct
14 Correct 2523 ms 76860 KB Output is correct
15 Correct 2479 ms 78404 KB Output is correct
16 Correct 2472 ms 79756 KB Output is correct
17 Correct 74 ms 4004 KB Output is correct
18 Correct 17 ms 760 KB Output is correct
19 Correct 1459 ms 22932 KB Output is correct
20 Correct 1477 ms 22904 KB Output is correct
21 Correct 120 ms 5420 KB Output is correct
22 Correct 2958 ms 106264 KB Output is correct
23 Incorrect 2981 ms 115440 KB Output isn't correct
24 Halted 0 ms 0 KB -