oj.uz

Submission #151506

# Submission time Handle Problem Language Result Execution time Memory
151506 2019-09-03T12:35:30 Z Mahotsukai Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 1095 ms 78036 KB 
#include<bits/stdc++.h>
#include<chrono>
using namespace std;
using namespace chrono;
#define all(a) a.begin(), a.end()
#define sz(x) (int(x.size()))
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;
	int ind;
	point(pll p): x(p.first), y(p.second){}
	point(ll x = 0, ll y = 0, int ind = 0): x(x), y(y), ind(ind){}
	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;
	}
};
ostream &operator<<(ostream &out, point p){
	cout << "(" << p.x << ", " << p.y << ", " << p.ind << ")";
	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, U, L;
	vector<point> ch, upper, lower;
	convhull(vector<point> arr = vector<point>()){
		if(arr.size() <= 1){
			ch = upper = lower = arr;
			N = U = L = arr.size();
			return;
		}
		sort(arr.begin(), arr.end());
		point p = arr.front(), q = arr.back();
		upper.push_back(p), lower.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]);
			}
			if(i == arr.size() - 1 || ori(p, arr[i], q) > 0){
				while(lower.size() >= 2 && ori(lower[lower.size() - 2], lower[lower.size() - 1], arr[i]) <= 0){
					lower.pop_back();
				}
				lower.push_back(arr[i]);
			}
		}
		U = upper.size(), L = lower.size();
		reverse(all(upper));
		for(int i = 0; i < L; i ++) ch.push_back(lower[i]);
		for(int i = 1; i < U - 1; i ++) ch.push_back(upper[i]);
		N = ch.size();
	}
	int max_element(ll x, ll y){
		point p(x, y);
		int l = 0, r = U;
		while(r - l > 3){
			int m1 = (2 * l + r) / 3, m2 = (l + 2 * r) / 3;
			p * upper[m1] <= p * upper[m2] ? l = m1 : r = m2;
		}
		int res = l;
		for(int i = l + 1; i < r; i ++) if(p * upper[res] < p * upper[i]) res = i;
		return (res + L - 1) % N;
	}
	int min_element(ll x, ll y){
		point p(x, y);
		int l = 0, r = L;
		while(r - l > 3){
			int m1 = (2 * l + r) / 3, m2 = (l + 2 * r) / 3;
			p * lower[m1] >= p * lower[m2] ? l = m1 : r = m2;
		}
		int res = l;
		for(int i = l + 1; i < r; i ++) if(p * lower[res] > p * lower[i]) res = i;
		return res;
	}
};
int n;
vector<vector<convhull>> c(2, vector<convhull>(2));
void Init(vi a, vi d, vi p){
	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], i), data[1][i] = point(d[i], p[i], i);
	for(int i = 0; i < 2; i ++){
		c[i][0] = convhull(data[i]);
		vi used(n);
		for(auto &p: c[i][0].ch) used[p.ind] = true;
		vector<point> temp;
		for(int j = 0; j < n; j ++) if(!used[j]) temp.push_back(data[i][j]);
		c[i][1] = convhull(temp);
	}
}
ll BestSquad(int x, int y){
	vector<vector<point>> p(2, vector<point>(2));
	point t(x, y);
	for(int i = 0; i < 2; i ++){
		int u = c[i][0].max_element(x, y), pu = (u + c[i][0].N - 1) % c[i][0].N, nu = (u + 1) % c[i][0].N;
		p[i][0] = c[i][0].ch[u];
		p[i][1] = t * c[i][0].ch[pu] <= t * c[i][0].ch[nu] ? c[i][0].ch[nu] : c[i][0].ch[pu];
		if(c[i][1].N){
			auto temp = c[i][1].ch[c[i][1].max_element(x, y)];
			if(t * p[i][1] < t * temp) p[i][1] = temp;
		}
	}
	if(p[0][0].ind == p[1][0].ind){
		return max((p[0][0] + p[1][1]) * t, (p[0][1] + p[1][0]) * t);
	}
	else{
		return (p[0][0] + p[1][0]) * t;
	}
}
/*
6 
2 1 1 
2 1 2 
2 1 3 
2 1 4 
2 1 5
2 1 6
100 

4 
3 1 4 
2 3 3 
2 1 6 
4 4 1 
2 
1 3 
3 1 
*/

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

Compilation message

squad.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::vector<_Tp>&)':
squad.cpp:32:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(auto &x: arr) out << x << ' '; cout << "\n";
  ^~~
squad.cpp:32: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:42:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(auto &x: arr) out << x << ' '; cout << "\n";
  ^~~
squad.cpp:42: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>)':
squad.cpp:89:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < arr.size(); i ++){
                  ~~^~~~~~~~~~~~
squad.cpp:90:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(i == arr.size() - 1 || ori(p, arr[i], q) < 0){
       ~~^~~~~~~~~~~~~~~~~
squad.cpp:96:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(i == arr.size() - 1 || ori(p, arr[i], q) > 0){
       ~~^~~~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 383 ms 44932 KB Output is correct
4 Correct 381 ms 44872 KB Output is correct
5 Correct 20 ms 4820 KB Output is correct
6 Correct 314 ms 69088 KB Output is correct
7 Correct 314 ms 69028 KB Output is correct
8 Correct 316 ms 69140 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 7 ms 884 KB Output is correct
3 Correct 616 ms 51412 KB Output is correct
4 Correct 618 ms 51448 KB Output is correct
5 Correct 27 ms 3128 KB Output is correct
6 Correct 771 ms 65600 KB Output is correct
7 Correct 798 ms 65496 KB Output is correct
8 Correct 772 ms 65640 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 383 ms 44932 KB Output is correct
4 Correct 381 ms 44872 KB Output is correct
5 Correct 20 ms 4820 KB Output is correct
6 Correct 314 ms 69088 KB Output is correct
7 Correct 314 ms 69028 KB Output is correct
8 Correct 316 ms 69140 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 7 ms 884 KB Output is correct
11 Correct 616 ms 51412 KB Output is correct
12 Correct 618 ms 51448 KB Output is correct
13 Correct 27 ms 3128 KB Output is correct
14 Correct 771 ms 65600 KB Output is correct
15 Correct 798 ms 65496 KB Output is correct
16 Correct 772 ms 65640 KB Output is correct
17 Correct 109 ms 5348 KB Output is correct
18 Correct 9 ms 944 KB Output is correct
19 Correct 680 ms 53624 KB Output is correct
20 Correct 671 ms 53668 KB Output is correct
21 Correct 37 ms 3600 KB Output is correct
22 Correct 1052 ms 78036 KB Output is correct
23 Correct 1095 ms 77916 KB Output is correct
24 Correct 1060 ms 77984 KB Output is correct