Submission #149094

#	Time	Username	Problem	Language	Result	Execution time	Memory
149094		还没编好 (#200)	Organizing the Best Squad (FXCUP4_squad)	C++17	0 / 100	12 ms	892 KiB

squad

#include "squad.h"
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
#include <assert.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 666666
typedef pair<ll,ll> pll;
ll operator * (pll a,pll b)
{
	return a.fi*b.se-a.se*b.fi;
}
pll operator - (pll a,pll b)
{
	return pll(a.fi-b.fi,a.se-b.se);
}
pll operator + (pll a,pll b)
{
	return pll(a.fi+b.fi,a.se+b.se);
}
vector<pll> convex_hull(vector<pll> p)
{
	sort(p.begin(),p.end());
	if(p.size()<=2) return p;
	vector<pll> h;
	for(int r=0;r<2;++r)
	{
		int l=h.size();
		for(auto x:p)
		{
			while((int)h.size()>l+1&&
			(h[h.size()-1]-h[h.size()-2])
			*(x-h[h.size()-2])<=0) h.pop_back();
			h.pb(x);
		}
		h.pop_back();
		reverse(p.begin(),p.end());
	}
	return h;
}
vector<pll> su(const vector<pll>& aa,const vector<pll>& bb)
{
//	vector<pll> g;
//	for(auto x:aa)
//	for(auto y:bb) g.pb(y+x);
//	g=convex_hull(g);
//	return g;
	static pll ans[SZ],a[SZ],b[SZ];
	int top,top1=aa.size(),top2=bb.size();
	for(int i=1;i<top1;++i) a[i]=aa[i]-aa[i-1];
	for(int i=1;i<top2;++i) b[i]=bb[i]-bb[i-1];
	a[top1]=aa[0]-aa[top1-1];
	b[top2]=bb[0]-bb[top2-1];
    //for(int i=1;i<=top1;i++)a[i]=stack1[i+1]-stack1[i];
    //for(int i=1;i<=top2;i++)b[i]=stack2[i+1]-stack2[i];
    ans[top=1]=aa[0]+bb[0];
    int now1=1,now2=1;
    while(now1<=top1&&now2<=top2)
		top++,ans[top]=ans[top-1]+
		((a[now1]*b[now2])>=0?a[now1++]:b[now2++]);
    while(now1<=top1)top++,ans[top]=ans[top-1]+a[now1++];
    while(now2<=top2)top++,ans[top]=ans[top-1]+b[now2++];
    top--;
	vector<pll> oo;
	for(int i=1;i<=top;++i) oo.pb(ans[i]);
	return oo;
}
int n,a[SZ],d[SZ],p[SZ];
vector<pll> op;
void go(int l,int r)
{
	if(l>=r) return;
	int m=(l+r)>>1;
	go(l,m); go(m+1,r);
	vector<pll> A,B,C,D;
	for(int i=l;i<=m;++i)
		A.pb(pll(a[i],p[i])),
		B.pb(pll(d[i],p[i]));
	for(int i=m+1;i<=r;++i)
		C.pb(pll(a[i],p[i])),
		D.pb(pll(d[i],p[i]));
	#define CH(w) w=convex_hull(w)
	CH(A);CH(B);CH(C);CH(D);
//	cout<<A.size()<<"w"<<B.size()<<"w"<<C.size()<<"w"<<D.size()<<"\n";
	A=su(A,D); B=su(B,C);
	for(auto t:A) op.pb(t);
	for(auto t:B) op.pb(t);
}
multimap<ld,pll> sb;
void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	n=A.size();
	for(int i=0;i<n;++i) a[i]=A[i],d[i]=D[i],p[i]=P[i];
	go(0,n-1);
//	for(auto u:op) cout<<u.fi<<","<<u.se<<"!";
//	cout<<"\n";
	op=convex_hull(op);
	for(int j=0;j<op.size();++j)
	{
		pll P=op[j],Q=op[j+1];
		sb.insert(mp((Q.se-P.se)/ld(Q.fi-P.fi),P));
	}
}

long long BestSquad(int X, int Y){
	auto w=sb.lower_bound(X/ld(Y));
	for(int j=1;j<=5&&w!=sb.begin();++j)
		--w;
	ll mx=0;
	for(int j=1;j<=10&&w!=sb.end();++j)
	{
		mx=max(mx,X*(ll)w->se.fi+Y*(ll)w->se.se);
		++w;
	}
	return mx;
}
#ifdef LOCAL
#include "grader.cpp"
#endif

Compilation message (stderr)

squad.cpp: In function 'void Init(std::vector<int>, std::vector<int>, std::vector<int>)':
squad.cpp:124:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<op.size();++j)
              ~^~~~~~~~~~

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