oj.uz

Submission #151508

# Submission time Handle Problem Language Result Execution time Memory
151508 2019-09-03T12:46:05 Z edenooo Organizing the Best Squad (FXCUP4_squad) C++17
19 / 100
 343 ms 42776 KB 
#include "squad.h"
#include<vector>
#include<algorithm>
using namespace std;

#define INF 9'000'000'000'000'000'000LL
#define ll long long

struct Fraction {
	ll a, b; // a/b
	bool operator< (Fraction &n)
	{
		if (a == -INF) return true; //틀린 이유
		if (n.a == -INF) return false;
		ll ta, tb, tc, td;
		ta = a; tb = b; tc = n.a; td = n.b;
		if (tb < 0) { ta *= -1; tb *= -1; }
		if (td < 0) { tc *= -1; td *= -1; }
		return ta * td < tb * tc;
	}
	bool operator<= (Fraction &n)
	{
		if (a == -INF) return true;
		if (n.a == -INF) return false;
		ll ta, tb, tc, td;
		ta = a; tb = b; tc = n.a; td = n.b;
		if (tb < 0) { ta *= -1; tb *= -1; }
		if (td < 0) { tc *= -1; td *= -1; }
		return ta * td <= tb * tc;
	}
};

struct Line {
	ll a, b;
	Fraction s;
	int idx;

	bool operator< (const Line &n) const
	{
		if (a != n.a) return a < n.a;
		return b > n.b;
	}
};

int N;
vector<Line> v, re;

Fraction Cross(Line &A, Line &B)
{
	return { (B.b - A.b),(A.a - B.a) };
}

struct CHT {
	vector<Line> cht;
	void insert(Line n)
	{
		while (!cht.empty())
		{
			if (cht.back().a == n.a)
			{
				if (cht.back().b <= n.b)
				{
					re.push_back(cht.back());
					cht.pop_back();
				}
				else return;
			}
			else
			{
				Fraction c = Cross(cht.back(), n);
				n.s.a = c.a; n.s.b = c.b;
				if (n.s <= cht.back().s) //틀린 이유
				{
					re.push_back(cht.back());
					cht.pop_back();
				}
				else break;
			}
		}
		cht.push_back(n);
	}
	int query(Fraction x)
	{
		if (cht.empty()) return -1;

		int lo = 0, hi = (int)cht.size();
		for (int i = 0; i < 20; i++)
		{
			int mid = lo + hi >> 1;
			if (x < cht[mid].s) hi = mid;
			else lo = mid;
		}
		return lo;
	}
} x, xx, y, yy;

void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	v.reserve(300301); re.reserve(300301);
	x.cht.reserve(300301); xx.cht.reserve(300301); y.cht.reserve(300301); yy.cht.reserve(300301);
	N = A.size();
	for (int i = 0; i < N; i++)
	{
		Line n = { (ll)A[i], (ll)P[i], {-INF, 1LL}, i }; //-INF : 틀린 이유
		v.push_back(n);
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++)
		x.insert(v[i]);

	sort(re.begin(), re.end());
	int M = (int)re.size();
	for (int i = 0; i < M; i++) //틀린 이유
		re[i].s = { -INF, 1LL };
	for (int i = 0; i < M; i++)
		xx.insert(re[i]);
	v.clear(); re.clear();

	for (int i = 0; i < N; i++)
	{
		Line n = { (ll)D[i], (ll)P[i], {-INF, 1LL}, i };
		v.push_back(n);
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++)
		y.insert(v[i]);
	sort(re.begin(), re.end());
	M = (int)re.size();
	for (int i = 0; i < M; i++)
		re[i].s = { -INF, 1LL };
	for (int i = 0; i < M; i++)
		yy.insert(re[i]);
	v.clear(); re.clear();
}

long long BestSquad(int X, int Y){
	Fraction pos = { (ll)X, (ll)Y };
	int i = x.query(pos);
	int j = y.query(pos);

	if (x.cht[i].idx != y.cht[j].idx)
		return x.cht[i].a*X + x.cht[i].b*Y + y.cht[j].a*X + y.cht[j].b*Y;
	else
	{
		ll res = 0;
		int ii = xx.query(pos);
		if (ii != -1)
			res = max(res, xx.cht[ii].a*X + xx.cht[ii].b*Y + y.cht[j].a*X + y.cht[j].b*Y);

		int jj = yy.query(pos);
		if (jj != -1)
			res = max(res, x.cht[i].a*X + x.cht[i].b*Y + yy.cht[jj].a*X + yy.cht[jj].b*Y);

		if (i - 1 >= 0)
			res = max(res, x.cht[i - 1].a*X + x.cht[i - 1].b*Y + y.cht[j].a*X + y.cht[j].b*Y);
		if (i + 1 < (int)x.cht.size())
			res = max(res, x.cht[i + 1].a*X + x.cht[i + 1].b*Y + y.cht[j].a*X + y.cht[j].b*Y);
		if (j - 1 >= 0)
			res = max(res, x.cht[i].a*X + x.cht[i].b*Y + y.cht[j - 1].a*X + y.cht[j - 1].b*Y);
		if (j + 1 < (int)y.cht.size())
			res = max(res, x.cht[i].a*X + x.cht[i].b*Y + y.cht[j + 1].a*X + y.cht[j + 1].b*Y);

		if (res == 0) while (1);
		return res;
	}
	return -1;
}

Compilation message

squad.cpp: In member function 'int CHT::query(Fraction)':
squad.cpp:89:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = lo + hi >> 1;
              ~~~^~~~
squad.cpp: In function 'void Init(std::vector<int>, std::vector<int>, std::vector<int>)':
squad.cpp:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++)
                  ~~^~~~~~~~~~
squad.cpp:124:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++)
                  ~~^~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 508 KB Output is correct
3 Correct 343 ms 42776 KB Output is correct
4 Correct 341 ms 42660 KB Output is correct
5 Correct 18 ms 3064 KB Output is correct
6 Correct 271 ms 42624 KB Output is correct
7 Correct 275 ms 42532 KB Output is correct
8 Correct 273 ms 42616 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 508 KB Output is correct
3 Correct 343 ms 42776 KB Output is correct
4 Correct 341 ms 42660 KB Output is correct
5 Correct 18 ms 3064 KB Output is correct
6 Correct 271 ms 42624 KB Output is correct
7 Correct 275 ms 42532 KB Output is correct
8 Correct 273 ms 42616 KB Output is correct
9 Incorrect 2 ms 376 KB Output isn't correct
10 Halted 0 ms 0 KB -