oj.uz

Submission #149698

# Submission time Handle Problem Language Result Execution time Memory
149698 2019-09-01T06:59:19 Z 서울대학교 연구공원 944동 삼성전자서울대연구소(#3600, ho94949, dotorya, zigui) Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 998 ms 38272 KB 
#include "squad.h"

#include<stdio.h>
#include<set>
#include<assert.h>
#include<queue>
#include<algorithm>
#include<vector>
#include<cmath>

using namespace std;

typedef long long ll;
typedef __int128 llll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<double, int> pdi;

const double EPS = 1e-8;
const double PI = acos(-1);

ll sq(ll x){ return x*x; }
ll size(pii x){ return sq(x.first) + sq(x.second); }

pii operator+(const pii &l, const pii &r){ return pii(l.first + r.first, l.second + r.second); }
pii operator-(const pii &l, const pii &r){ return pii(l.first - r.first, l.second - r.second); }
ll operator^(const pii &l, const pii &r){ return (ll)l.first * r.second - (ll)l.second * r.first; }
ll operator/(const pii &l, const pii &r){ return (ll)l.first * r.second - (ll)l.second * r.first; }
ll operator*(const pii &l, const pii &r){ return (ll)l.first * r.first + (ll)l.second * r.second; }
pii operator*(const pii &l, const int &r){ return pii(l.first * r, l.second * r); }
pii operator-(const pii &l){ return pii(-l.first, -l.second); }

struct point{
	point(pii p, int d):p(p), d(d){}
	pii p;
	int d;
};

vector<point> P, Q, U, V;

void convex(vector<point> D, vector<point> &A, vector<point> &B, bool rec = true)
{
	if(D.size() == 0) return;

	sort(D.begin(), D.end(), [](point l, point r){
		return l.p < r.p;
	});

	vector<point> E;
	for(point c : D){
		while(A.size() >= 2 && (A[A.size()-2].p - A.back().p) / (c.p - A.back().p) <= 0 ){
			E.push_back(A.back());
			A.pop_back();
		}
		A.push_back(c);
	}
	vector<point> tmp;
	if(rec) convex(E, B, tmp, false); 
}

void print(point c){
	printf("%d : (%d,%d)\n", c.d, c.p.first, c.p.second);
}

struct answer{
	answer(){
		m1 = m2 = -1;
		v1 = v2 = -1;
	}
	int m1; ll v1;
	int m2; ll v2;

	void apply(ll v, int m){
		if(v1 < v){
			v2 = v1, m2 = m1;
			v1 = v, m1 = m;
		}
		else if(v2 < v && m1 != m){
			v2 = v, m2 = m;
		}
	}
};

void Init(std::vector<int> A, std::vector<int> D, std::vector<int> Z){
	int N = A.size();
	vector<point> D1, D2;
	for(int i = 0; i < N; i++) D1.emplace_back(pii(A[i], Z[i]), i);
	for(int i = 0; i < N; i++) D2.emplace_back(pii(D[i], Z[i]), i);

	convex(D1, P, Q);
	convex(D2, U, V);
/*
	for(point c : P) print(c); printf("\n");
	for(point c : Q) print(c); printf("\n");
	for(point c : U) print(c); printf("\n");
	for(point c : V) print(c); printf("\n");
// */
}

void getanswer(vector<point> &D, int X, int Y, answer &ans)
{
	auto F = [](pii p, int X, int Y){
		return (ll)p.first * X + (ll)p.second * Y;
	};
	int s = 0, e = (int)D.size()-1;
	while(e-s >= 3){
		int m1 = (s*2+e) / 3;
		int m2 = (s+e*2) / 3;
		
		ll p = F(D[m1].p, X, Y);
		ll q = F(D[m2].p, X, Y);
		if(p > q) e = m2;
		else s = m1;
	}
	for(int i = s-1; i <= e+1; i++){
		if(0 <= i && i < D.size()) ans.apply(F(D[i].p, X, Y), D[i].d);
	}
}

long long BestSquad(int X, int Y){
	answer a = answer(), d = answer();
	getanswer(P, X, Y, a);
	getanswer(Q, X, Y, a);
	getanswer(U, X, Y, d);
	getanswer(V, X, Y, d);
	if(a.m1 == d.m1){
		return max(a.v1 + d.v2, a.v2 + d.v1);
	}
	else return a.v1 + d.v1;
}

Compilation message

squad.cpp: In function 'void getanswer(std::vector<point>&, int, int, answer&)':
squad.cpp:116:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(0 <= i && i < D.size()) ans.apply(F(D[i].p, X, Y), D[i].d);
                ~~^~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 333 ms 35756 KB Output is correct
4 Correct 339 ms 35884 KB Output is correct
5 Correct 20 ms 2316 KB Output is correct
6 Correct 256 ms 31232 KB Output is correct
7 Correct 255 ms 30976 KB Output is correct
8 Correct 262 ms 31232 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 10 ms 764 KB Output is correct
3 Correct 530 ms 35880 KB Output is correct
4 Correct 511 ms 35872 KB Output is correct
5 Correct 28 ms 1840 KB Output is correct
6 Correct 567 ms 38228 KB Output is correct
7 Correct 563 ms 38272 KB Output is correct
8 Correct 591 ms 38272 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 333 ms 35756 KB Output is correct
4 Correct 339 ms 35884 KB Output is correct
5 Correct 20 ms 2316 KB Output is correct
6 Correct 256 ms 31232 KB Output is correct
7 Correct 255 ms 30976 KB Output is correct
8 Correct 262 ms 31232 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 10 ms 764 KB Output is correct
11 Correct 530 ms 35880 KB Output is correct
12 Correct 511 ms 35872 KB Output is correct
13 Correct 28 ms 1840 KB Output is correct
14 Correct 567 ms 38228 KB Output is correct
15 Correct 563 ms 38272 KB Output is correct
16 Correct 591 ms 38272 KB Output is correct
17 Correct 87 ms 2808 KB Output is correct
18 Correct 14 ms 768 KB Output is correct
19 Correct 606 ms 35872 KB Output is correct
20 Correct 587 ms 35872 KB Output is correct
21 Correct 34 ms 1636 KB Output is correct
22 Correct 952 ms 31152 KB Output is correct
23 Correct 998 ms 31236 KB Output is correct
24 Correct 950 ms 31252 KB Output is correct