Submission #149354

#	Time	Username	Problem	Language	Result	Execution time	Memory
149354		Powered By Zigui (#200)	Organizing the Best Squad (FXCUP4_squad)	C++17	100 / 100	725 ms	27236 KiB

squad

#include "squad.h"
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define INF  (1<<30)
#define INFL (1LL<<60)
#define EPS ((ld)(1e-9))
 
#define sz(x) ((int)(x).size())
#define setz(x) memset(x, 0, sizeof(x))
#define all(x) (x).begin(), (x).end()
#define rep(i, e) for (int i = 0, _##i = (e); i < _##i; i++)
#define repp(i, s, e) for (int i = (s), _##i = (e); i < _##i; i++)
#define repr(i, s, e) for (int i = (s)-1, _##i = (e); i >= _##i; i--)
#define repi(i, x) for (auto &i : (x))
#define ARR(...) vector<int>({__VA_ARGS__})
#define ARS(...) vector<string>({__VA_ARGS__})
 
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
//typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
 
struct pii {
	int fi, se;
	int idx;
};

ostream &operator<<(ostream &os, const pii pai) { 
    return os << '(' << pai.first << ' ' << pai.second << ' ' << pai.idx << ')';
}
 
template<typename T>
ostream &operator<<(ostream &os, const vector<T> v) {
    cout << '[';
    for (auto p : v) cout << p << ",";
    cout << "]";
    return os;
}
 
template<typename T, typename V>
ostream &operator<<(ostream &os, const set<T, V> v) {
    cout << "{";
    for (auto p : v) cout << p << ",";
    cout << "}";
    return os;
}
 
template<typename T, typename V>
ostream &operator<<(ostream &os, const map<T, V> v) {
    cout << "{";
    for (auto p : v) cout << p << ",";
    cout << "}";
    return os;
}
 
#ifndef __SOULTCH
#define debug(...) 0
#define endl '\n'
#else
#define debug(...) cout << " [-] ", _dbg(#__VA_ARGS__, __VA_ARGS__)
template<class TH> void _dbg(const char *sdbg, TH h){ cout << sdbg << '=' << h << endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
    while(*sdbg != ',') cout << *sdbg++;
    cout << '=' << (h) << ','; 
    _dbg(sdbg+1, a...);
}
#endif
 
template<typename T> void get_max(T &a, T b) {a = max(a, b);}
template<typename T> void get_min(T &a, T b) {a = min(a, b);}

int ccw(pii a, pii b, pii c) {
	ll v1 = (ll)a.fi*b.se + (ll)b.fi*c.se + (ll)c.fi*a.se;
	ll v2 = (ll)a.se*b.fi + (ll)b.se*c.fi + (ll)c.se*a.fi;
	
	if (v1 > v2) return 1;
	if (v1 < v2) return -1;
	return 0;
}

ll norm(pii a) {
	return (ll)a.fi*a.fi + (ll)a.se*a.se;
}

bool cmp_d(int a, int b, int c, int d) {
	return (ll)a*d < (ll)c*b;
}


struct Convex {
	vector<pii> pt;	

	vector<pii> build(vector<pii> &cand) {
		if (sz(cand) == 0) {
			pt.push_back({0, 0, -1});
			return vector<pii>();
		}
		vector<pii> res;
		
		int max_X = 0, max_Y = 0;
		
		rep(i, sz(cand)) get_max(max_X, cand[i].fi), get_max(max_Y, cand[i].se);
		cand.push_back({max_X, 0, -1});
		cand.push_back({0, max_Y, -1});
		
		auto p = min_element(all(cand), [](pii a, pii b) {return a.fi < b.fi;});
		if (p != cand.begin()) swap(*p, cand[0]);
		
		sort(cand.begin()+1, cand.end(), [&](pii a, pii b) {
			int v = ccw(cand[0], a, b);
			if (v) return v == -1;
			return norm(a) < norm(b);
		});
		
		int pos = 0;
		for (pos = 1; pos < sz(cand) and cand[pos].idx >= 0; pos++); 
		
		rep(i, pos+1) {
			while(sz(pt) > 1 and ccw(pt[sz(pt)-2], pt[sz(pt)-1], cand[i]) != -1) res.push_back(pt.back()), pt.pop_back();
			pt.push_back(cand[i]);
		}
		repp(i, pos+1, sz(cand)) res.push_back(cand[i]);
		return res;
	}


	int query(int X, int Y) {
		int l = 0, r = sz(pt)-2;
		while(l < r) {
			int mid = (l+r)/2;
			if (cmp_d(pt[mid+1].fi-pt[mid].fi, pt[mid].se-pt[mid+1].se, Y, X)) r = mid;
			else l = mid+1;
		}
		return l;
	}
};

int N;
Convex A1, A2;
Convex B1, B2;

ll calc(pii p, int X, int Y) {
	return (ll)p.fi*X + (ll)p.se*Y;
}


void Init(vector<int> A, vector<int> D, vector<int> P){
	N = sz(A);
	vector<pii> AA, BB;
	rep(i, N) AA.push_back({A[i], P[i], i});
	rep(i, N) BB.push_back({D[i], P[i], i});
	
	AA = A1.build(AA); A2.build(AA);
	BB = B1.build(BB); B2.build(BB);
}

long long BestSquad(int X, int Y){
	int a1 = A1.query(X, Y);
	int b1 = B1.query(X, Y);
	
	pii x1 = A1.pt[a1], y1 = B1.pt[b1];
	
	debug(x1, y1);
	
	if (x1.idx != y1.idx) return calc(x1, X, Y)+calc(y1, X, Y);
	
	pii c1 = A2.pt[A2.query(X, Y)], d1 = B2.pt[B2.query(X, Y)];
	
	if (a1 > 1           and calc(c1, X, Y) < calc(A1.pt[a1-1], X, Y)) c1 = A1.pt[a1-1];
	if (a1 < sz(A1.pt)-2 and calc(c1, X, Y) < calc(A1.pt[a1+1], X, Y)) c1 = A1.pt[a1+1];
	
	if (b1 > 1           and calc(d1, X, Y) < calc(B1.pt[b1-1], X, Y)) d1 = B1.pt[b1-1];
	if (b1 < sz(B1.pt)-2 and calc(d1, X, Y) < calc(B1.pt[b1+1], X, Y)) d1 = B1.pt[b1+1];
	
	debug(x1, d1);
	debug(y1, c1);
	
	return max(calc(x1, X, Y)+calc(d1, X, Y), calc(y1, X, Y)+calc(c1, X, Y));
}

Compilation message (stderr)

squad.cpp: In function 'long long int BestSquad(int, int)':
squad.cpp:173:15: warning: statement has no effect [-Wunused-value]
  debug(x1, y1);
               ^
squad.cpp:185:15: warning: statement has no effect [-Wunused-value]
  debug(x1, d1);
               ^
squad.cpp:186:15: warning: statement has no effect [-Wunused-value]
  debug(y1, c1);
               ^

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