oj.uz

Submission #150523

# Submission time Handle Problem Language Result Execution time Memory
150523 2019-09-01T08:34:52 Z 본인 하지만 안 어림 ㅋㅋ(#3569, gs13105, xdoju, gs13068) Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 1112 ms 53136 KB 
#include "squad.h"
#include <cstdio>
#include <algorithm>

using namespace std;

typedef pair<int, int> p;
typedef pair<p, int> pp;

pp a[300003];
vector<pp> AA, DD;
vector<p> AAA[300003], DDD[300003];

inline long long ccw(p &u, p &v, p &w) {
	return (long long)(w.first - u.first) * (v.second - u.second) - (long long)(w.second - u.second) * (v.first - u.first);
}

inline long long ccw(pp &u, pp &v, pp &w) {
	return ccw(u.first, v.first, w.first);
}

inline void create(int N, vector<int> &A, vector<int> &P, vector<pp> &r, vector<p> *s) {
	int i, j;
	for (i = 0; i < N; i++) {
		a[i].first.first = A[i];
		a[i].first.second = P[i];
		a[i].second = i;
	}
	sort(a, a + N);
	for (i = 0; i < N; i++) {
		while (!r.empty() && r[r.size() - 1].first.first <= a[i].first.first && r[r.size() - 1].first.second <= a[i].first.second || r.size() > 1 && ccw(r[r.size() - 2], r[r.size() - 1], a[i]) <= 0) r.pop_back();
		r.push_back(a[i]);
	}
	for (i = 0; i < r.size(); i++) {
		auto L = i ? lower_bound(a, a + N, r[i - 1]) : a, R = i + 1 < r.size() ? upper_bound(a, a + N, r[i + 1]) : a + N;
		auto &t = s[r[i].second];
		for (; L < R; L++) {
			if (*L == r[i]) continue;
			while (!t.empty() && t[t.size() - 1].first <= L->first.first && t[t.size() - 1].second <= L->first.second || t.size() > 1 && ccw(t[t.size() - 2], t[t.size() - 1], L->first) <= 0) t.pop_back();
			t.push_back(L->first);
		}
	}
}

void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	int N = A.size();
	create(N, A, P, AA, AAA);
	create(N, D, P, DD, DDD);
	//for (auto t : AA) printf("%d %d %d\n", t.first.first, t.first.second, t.second); puts("");
	//for (auto t : DD) printf("%d %d %d\n", t.first.first, t.first.second, t.second); puts("");
	//for (int i = 0; i < N; i++) if (!AAA[i].empty()) { printf("%d : ", i); for (auto t : AAA[i]) printf("(%d %d) ", t.first, t.second); puts(""); }
	//for (int i = 0; i < N; i++) if (!DDD[i].empty()) { printf("%d : ", i); for (auto t : DDD[i]) printf("(%d %d) ", t.first, t.second); puts(""); }
}

inline pp bs(vector<pp> &AA, long long X, long long Y) {
	int L = 0, R = AA.size() - 1;
	while (L < R) {
		int M = L + R >> 1;
		if (X * AA[M].first.first + Y * AA[M].first.second < X * AA[M + 1].first.first + Y * AA[M + 1].first.second) L = M + 1;
		else R = M;
	}
	return AA[L];
}

inline p bs(vector<p> &AAA, long long X, long long Y) {
	int L = 0, R = AAA.size() - 1;
	while (L < R) {
		int M = L + R >> 1;
		if (X * AAA[M].first + Y * AAA[M].second < X * AAA[M + 1].first + Y * AAA[M + 1].second) L = M + 1;
		else R = M;
	}
	return AAA[L];
}

long long BestSquad(int X, int Y){
	auto A = bs(AA, X, Y), D = bs(DD, X, Y);
	//printf("%d %d %d, %d %d %d\n", A.first.first, A.first.second, A.second, D.first.first, D.first.second, D.second);
	if (A.second != D.second) return 1ll * X * (A.first.first + D.first.first) + 1ll * Y * (A.first.second + D.first.second);
	auto A2 = bs(AAA[A.second], X, Y), D2 = bs(DDD[D.second], X, Y);
	return max(
		1ll * X * (A.first.first + D2.first) + 1ll * Y * (A.first.second + D2.second),
		1ll * X * (D.first.first + A2.first) + 1ll * Y * (D.first.second + A2.second)
	);
}

Compilation message

squad.cpp: In function 'void create(int, std::vector<int>&, std::vector<int>&, std::vector<std::pair<std::pair<int, int>, int> >&, std::vector<std::pair<int, int> >*)':
squad.cpp:31:72: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   while (!r.empty() && r[r.size() - 1].first.first <= a[i].first.first && r[r.size() - 1].first.second <= a[i].first.second || r.size() > 1 && ccw(r[r.size() - 2], r[r.size() - 1], a[i]) <= 0) r.pop_back();
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
squad.cpp:34:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < r.size(); i++) {
              ~~^~~~~~~~~~
squad.cpp:35:63: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   auto L = i ? lower_bound(a, a + N, r[i - 1]) : a, R = i + 1 < r.size() ? upper_bound(a, a + N, r[i + 1]) : a + N;
                                                         ~~~~~~^~~~~~~~~~
squad.cpp:39:65: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    while (!t.empty() && t[t.size() - 1].first <= L->first.first && t[t.size() - 1].second <= L->first.second || t.size() > 1 && ccw(t[t.size() - 2], t[t.size() - 1], L->first) <= 0) t.pop_back();
           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
squad.cpp:23:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
squad.cpp: In function 'pp bs(std::vector<std::pair<std::pair<int, int>, int> >&, long long int, long long int)':
squad.cpp:58:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int M = L + R >> 1;
           ~~^~~
squad.cpp: In function 'p bs(std::vector<std::pair<int, int> >&, long long int, long long int)':
squad.cpp:68:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int M = L + R >> 1;
           ~~^~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14464 KB Output is correct
2 Correct 15 ms 14464 KB Output is correct
3 Correct 262 ms 24952 KB Output is correct
4 Correct 263 ms 25080 KB Output is correct
5 Correct 41 ms 16884 KB Output is correct
6 Correct 496 ms 50904 KB Output is correct
7 Correct 505 ms 50896 KB Output is correct
8 Correct 494 ms 50640 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14464 KB Output is correct
2 Correct 17 ms 14592 KB Output is correct
3 Correct 409 ms 27316 KB Output is correct
4 Correct 413 ms 27344 KB Output is correct
5 Correct 36 ms 15672 KB Output is correct
6 Correct 608 ms 40088 KB Output is correct
7 Correct 635 ms 40092 KB Output is correct
8 Correct 614 ms 40088 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14464 KB Output is correct
2 Correct 15 ms 14464 KB Output is correct
3 Correct 262 ms 24952 KB Output is correct
4 Correct 263 ms 25080 KB Output is correct
5 Correct 41 ms 16884 KB Output is correct
6 Correct 496 ms 50904 KB Output is correct
7 Correct 505 ms 50896 KB Output is correct
8 Correct 494 ms 50640 KB Output is correct
9 Correct 14 ms 14464 KB Output is correct
10 Correct 17 ms 14592 KB Output is correct
11 Correct 409 ms 27316 KB Output is correct
12 Correct 413 ms 27344 KB Output is correct
13 Correct 36 ms 15672 KB Output is correct
14 Correct 608 ms 40088 KB Output is correct
15 Correct 635 ms 40092 KB Output is correct
16 Correct 614 ms 40088 KB Output is correct
17 Correct 91 ms 16888 KB Output is correct
18 Correct 19 ms 14592 KB Output is correct
19 Correct 427 ms 27316 KB Output is correct
20 Correct 429 ms 27320 KB Output is correct
21 Correct 46 ms 16376 KB Output is correct
22 Correct 1055 ms 53136 KB Output is correct
23 Correct 1112 ms 53008 KB Output is correct
24 Correct 1109 ms 53132 KB Output is correct