Submission #149864

#	Time	Username	Problem	Language	Result	Execution time	Memory
149864		TeamSUA (#200)	Organizing the Best Squad (FXCUP4_squad)	C++17	0 / 100	3099 ms	30368 KiB

squad

#include "squad.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const double eps = 1e-8;

#ifndef DEBUGGGG
#define DEBUGGGG 1
#endif

vector<int> __a, __d, __p;

void initbf(std::vector<int> A, std::vector<int> D, std::vector<int> P) {
	__a = A;
	__d = D;
	__p = P;
}

ll bfbfb(int X, int Y) {
	ll ans = 0;
	int n = __a.size();
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++) 
			if (i != j) {
				ans = max(ans, 1ll * X * (__a[i] + __d[j]) + 1ll * Y * (__p[i] + __p[j]));
			}
	}
	return ans;
}

struct Pt{
	long long x, y;
	int idx;
};

bool operator < (const Pt & a, const Pt & b){
	if (a.x == b.x)
		return a.y < b.y;
	else
		return a.x < b.x;
}

bool operator == (const Pt & a, const Pt & b){
	return a.x == b.x && a.y == b.y;
}

inline long long operator * (const Pt & a, const Pt & b){
	return a.x * b.y - a.y * b.x;
}

inline long long operator % (const Pt & a, const Pt & b){
	return a.x * b.x + a.y * b.y;
}

inline Pt operator - (const Pt & a, const Pt & b){
	return (Pt){a.x - b.x, a.y - b.y, 0};
}

inline Pt operator + (const Pt & a, const Pt & b){
	return (Pt){a.x + b.x, a.y + b.y, 0};
}

long long sqr(long long x){
	return x * x;
}

inline double len(const Pt & a){
	return sqrt(sqr(a.x) + sqr(a.y));
}

long long absll(long long x){
	return x < 0 ? -x : x;
}

vector<Pt> convex_hull(vector<Pt> u){
    sort(u.begin(), u.end()); 
    u.erase(unique(u.begin(), u.end()), u.end()); 
    if (u.size() < 3) 
		    return u;
    vector<Pt> c;
    for(int i=0, o=1, m=1; ~i; i += o){
        while(c.size() > m){
            Pt a = c.back() - c[c.size() - 2];
            Pt b = c.back() - u[i];
            if (a * b <= 0) 
							break; 
            c.pop_back();
        }
        c.push_back(u[i]);
        if(i + 1 == u.size()) 
			m = c.size(), o = -1;
    }
    c.pop_back();
    return c;
}

vector<Pt> a1, a2, b1, b2;

void fuck(vector<Pt> &a) {
	// cout << "fuck" << endl;
	a = convex_hull(a);
	// for (auto &pt : a) cout << pt.x << ' ' << pt.y << endl;
	// cout << "===" << endl;
	if (a.size() < 4) return ;
	int u = 0, v = 0;
	vector<Pt> b;
	for (int i = 1; i < a.size(); i++) {
		if (a[i].x > a[u].x || (a[i].x == a[u].x && a[i].y < a[u].y))
			u = i;
		if (a[i].y > a[v].y || (a[i].y == a[v].y && a[i].x < a[v].x))
			v = i;
	}
	for (int i = u; i != v; i = (i + 1) % a.size()) {
		b.push_back(a[i]);
	}
	b.push_back(a[v]);
	a.swap(b);
	// for (auto &pt : a) cout << pt.x << ' ' << pt.y << endl;
	// cout << "QAQ" << endl;
}

void deal(const vector<int>& A, const vector<int>& P, 
		vector<Pt>& a, vector<Pt>& b) {
	int n = A.size();
	a.resize(n);
	for (int i = 0; i < n; i++) {
		a[i].x = A[i];
		a[i].y = P[i];
		a[i].idx = i;
	}
	fuck(a);
	vector<int> vis;
	for (auto &x : a) {
		vis.push_back(x.idx);
	}
	sort(vis.begin(), vis.end());
	vis.push_back(n + 1);
	b.clear();
	for (int i = 0, j = 0; i < n; i++) {
		if (vis[j] == i) j++;
		else {
			b.push_back((Pt){A[i], P[i], i});
		}
	}
	fuck(b);
}

std::vector<Pt> query1(ll X, ll Y, const vector<Pt>& a) {
	int L = 0, R = a.size() - 1;
	while (L + 5 < R) {
		int M = (L + R) / 2;
		int M2 = (L + M) / 2;
		ll ans1 = a[M].x * X + a[M].y * Y;
		ll ans2 = a[M2].x * X + a[M2].y * Y;
		if (ans1 > ans2) {
			L = M2;
		}
		else {
			R = M;
		}
	}
	L = max(0, L - 1);
	R = min(R + 1, int(a.size()) - 1);
	Pt u({0, 0, 0});
	Pt v({0, 0, 0});
	for (int i = L; i <= R; i++) {
		ll ans = a[i].x * X + a[i].y * Y;
		if (ans > u.x) {
			v = u;
			u.idx = a[i].idx;
			u.x = ans;
		}
		else if (ans > v.x) {
			v.idx = a[i].idx;
			v.x = ans;
		}
	}
	vector<Pt> ans;
	ans.push_back(u);
	ans.push_back(v);
	return ans;
}

std::vector<Pt> query(ll X, ll Y, const vector<Pt>& a, const vector<Pt>& b) {
	auto u = query1(X, Y, a);
	auto v = query1(X, Y, b);
	for (auto & pt : v) u.push_back(pt);
	return u;
}

void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	if (DEBUGGGG)
		initbf(A,D,P);
	int n = A.size();
	deal(A, P, a1, a2);
	deal(D, P, b1, b2);
	// for (auto &x : a1) cout << x.x << ' ' << x.y << ' ' << x.idx << endl; cout << endl;
	// for (auto &x : a2) cout << x.x << ' ' << x.y << ' ' << x.idx << endl; cout << endl;
	// for (auto &x : b1) cout << x.x << ' ' << x.y << ' ' << x.idx << endl; cout << endl;
	// for (auto &x : b2) cout << x.x << ' ' << x.y << ' ' << x.idx << endl; cout << endl;
}

long long BestSquad(int X, int Y){
	if (DEBUGGGG)
		return bfbfb(X, Y);
	auto u = query(X, Y, a1, a2);
	auto v = query(X, Y, b1, b2);
	ll ans = 0;
	for (auto &p : u) {
		for (auto &q : v) {
			if (p.idx != q.idx) {
				ans = max(ans, p.x + q.x);
			}
		}
	}
	return ans;
}

Compilation message (stderr)

squad.cpp: In function 'std::vector<Pt> convex_hull(std::vector<Pt>)':
squad.cpp:83:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(c.size() > m){
               ~~~~~~~~~^~~
squad.cpp:91:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i + 1 == u.size())
            ~~~~~~^~~~~~~~~~~
squad.cpp: In function 'void fuck(std::vector<Pt>&)':
squad.cpp:108:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < a.size(); i++) {
                  ~~^~~~~~~~~~
squad.cpp: In function 'void Init(std::vector<int>, std::vector<int>, std::vector<int>)':
squad.cpp:195:6: warning: unused variable 'n' [-Wunused-variable]
  int n = A.size();
      ^

• Subtask 1: 0 / 19
• Subtask 2: 0 / 28
• Subtask 3: 0 / 53