oj.uz

Submission #149554

# Submission time Handle Problem Language Result Execution time Memory
149554 2019-09-01T06:43:04 Z 서울대학교 연구공원 944동 삼성전자서울대연구소(#3600, ho94949, dotorya, zigui) Organizing the Best Squad (FXCUP4_squad) C++17
0 / 100
 6 ms 384 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;
	int mn = 0;
	for(int i = 1; i < D.size(); i++){
		if(D[mn].p > D[i].p) mn = i;
	}
	swap(D[mn], D[0]);
	pii t = D[0].p;
	for(int i = 0; i < D.size(); i++)	D[i].p = D[i].p - t;
	sort(D.begin()+1, D.end(), [](point l, point r){
		if(l.p/r.p != 0 ) return l.p/r.p < 0;
		return size(l.p) < size(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(c);
			A.pop_back();
		}
		A.push_back(c);
	}
	for(point &c : A) c.p = c.p + t;
	for(point &c : E) c.p = c.p + t;
	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), i);
	}
}

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 convex(std::vector<point>, std::vector<point>&, std::vector<point>&, bool)':
squad.cpp:45:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < D.size(); i++){
                 ~~^~~~~~~~~~
squad.cpp:50:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < D.size(); i++) D[i].p = D[i].p - t;
                 ~~^~~~~~~~~~
squad.cpp: In function 'void getanswer(std::vector<point>&, int, int, answer&)':
squad.cpp:125: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), i);
                ~~^~~~~~~~~~

Subtask #1
0 / 19.0

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

Subtask #2
0 / 28.0

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

Subtask #3
0 / 53.0

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