Submission #149374

#	Time	Username	Problem	Language	Result	Execution time	Memory
149374		잉여로운 고3 (#200)	Organizing the Best Squad (FXCUP4_squad)	C++17	100 / 100	869 ms	27516 KiB

squad

#include "squad.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300010;

typedef long long lint;

struct DOT {
	int x, y, idx;

	DOT(int x = 0, int y = 0, int idx = 0) : x(x), y(y), idx(idx) {}

	bool operator < (DOT a) const { return x != a.x ? x < a.x : y > a.y; }
};

int N;
vector<DOT> att[2], def[2];
bool bo[MAXN];

lint cp(DOT a, DOT b) { return lint(a.x) * b.y - lint(a.y) * b.x; }
lint ccw(DOT a, DOT b, DOT c) {
	return cp(a, b) + cp(b, c) + cp(c, a);
}

void gch(int N, vector<DOT> &v, vector<DOT> &ch) {
	if(!N) return;
	int t = 0;
	for(int i = 0; i < N; i++) if(v[i].y >= v[t].y) t = i;
	ch.push_back(v[t]);
	for(int i = t + 1; i < N; i++) {
		while(ch.size() > 1 && ccw(ch[ch.size() - 2], ch.back(), v[i]) >= 0) ch.pop_back();
		ch.push_back(v[i]);
	}
	for(auto a : ch) bo[a.idx] = true;
}

void gbest(int N, vector<DOT> &v, vector<DOT> &b1, vector<DOT> &b2) {
	for(int i = 0; i < N; i++) bo[i] = false;
	sort(v.begin(), v.end());
	//for(auto a : v) printf("(%d, %d, %d)\n", a.x, a.y, a.idx);
	//printf("\n");
	gch(N, v, b1);
	vector<DOT> v2;
	for(auto a : v) if(!bo[a.idx]) v2.push_back(a);
	gch(v2.size(), v2, b2);

	/*
	for(auto a : b1) printf("(%d, %d, %d)\n", a.x, a.y, a.idx);
	printf("\n");
	for(auto a : b2) printf("(%d, %d, %d)\n", a.x, a.y, a.idx);
	printf("\n\n");
	*/
}

void Init(vector<int> AA, vector<int> DD, vector<int> P){
	N = AA.size();
	vector<DOT> A, D;
	for(int i = 0; i < N; i++) {
		A.emplace_back(AA[i], P[i], i);
		D.emplace_back(DD[i], P[i], i);
	}
	gbest(N, A, att[0], att[1]);
	gbest(N, D, def[0], def[1]);
}

lint calc(DOT a, int X, int Y) {
	return lint(a.x) * X + lint(a.y) * Y;
}

int tri(vector<DOT> &ch, int X, int Y) {
	int s = 0, e = ch.size() - 1; 
	while(s < e) {
		//printf("s = %d, e = %d\n", s, e);
		int m1 = (s * 2 + e) / 3;
		int m2 = (s + 2 * e + 1) / 3;
		lint t1 = calc(ch[m1], X, Y);
		lint t2 = calc(ch[m2], X, Y);
		if(t1 < t2) s = m1 + 1;
		else e = m2 - 1;
	}
	return s;
}

void gbest2(vector<DOT> &b1, vector<DOT> &b2, int &r1, int &r2, lint &c1, lint &c2, int X, int Y) {
	int t = tri(b1, X, Y);
	//printf("t = %d\n", t);
	r1 = b1[t].idx;
	c1 = calc(b1[t], X, Y);
	c2 = -1;
	if(t > 0) {
		r2 = b1[t - 1].idx;
		c2 = calc(b1[t - 1], X, Y);
	}
	if(t < b1.size() - 1) if(c2 < calc(b1[t + 1], X, Y)) {
		c2 = calc(b1[t + 1], X, Y);
		r2 = b1[t + 1].idx;
	}
	if(!b2.empty()) {
		int t2 = tri(b2, X, Y);
		if(c2 < calc(b2[t2], X, Y)) {
			c2 = calc(b2[t2], X, Y);
			r2 = b2[t2].idx;
		}
	}
}

long long BestSquad(int X, int Y){
	int a1, a2, d1, d2;
	lint ac1, ac2, dc1, dc2;
	gbest2(att[0], att[1], a1, a2, ac1, ac2, X, Y);
	//printf("%d %d %lld %lld\n", a1, a2, ac1, ac2);
	gbest2(def[0], def[1], d1, d2, dc1, dc2, X, Y);
	//printf("%d %d %lld %lld\n", d1, d2, dc1, dc2);
	return a1 != d1 ? ac1 + dc1 : max(ac1 + dc2, ac2 + dc1);
}

Compilation message (stderr)

squad.cpp: In function 'void gbest2(std::vector<DOT>&, std::vector<DOT>&, int&, int&, lint&, lint&, int, int)':
squad.cpp:95:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(t < b1.size() - 1) if(c2 < calc(b1[t + 1], X, Y)) {
     ~~^~~~~~~~~~~~~~~

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