제출 #150662

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
150662		본인 방금 올솔하는 상상함 (#200)	최적의 팀 구성 (FXCUP4_squad)	C++17	0 / 100	6 ms	512 KiB

squad

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

struct Point{
	long long x, y;
	int ind;
	bool operator <(const Point A) const{
		if(x==A.x) return y<A.y;
		return x<A.x;
	}
};
vector<Point> pa,pb,ca,cb,cca,ccb;
int n;
bool in[300010];
bool chk(Point a, Point b, Point c){
	long long x=b.x-a.x, y=b.y-a.y, xx=c.x-b.x, yy=c.y-b.y;
	return x*yy-y*xx>=0;
}
vector<Point> f(vector<Point> feed){
	vector<Point> ret;
	for(auto i:feed){
		while(!ret.empty()&&ret[ret.size()-1].x==i.x&&ret[ret.size()-1].y<=i.y){
			in[ret[ret.size()-1].ind]=false;
			ret.pop_back();
		}
		while(ret.size()>1&&chk(ret[ret.size()-2],ret[ret.size()-1],i)) ret.pop_back();
		ret.push_back(i);
		in[i.ind]=true;
	}
	return ret;
}
void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	n = A.size();
	for(int i=0;i<n;i++){
		pa.push_back({A[i],P[i],i});
		pb.push_back({D[i],P[i],i});
	}
	sort(pa.begin(), pa.end());
	sort(pb.begin(), pb.end());
	for(int i=0;i<n;i++) in[i]=false;
	ca = f(pa);
	for(auto i:pa){
		if(in[i.ind]==false) cca.push_back(i);
		in[i.ind]=false;
	}
	cca = f(cca);
	for(int i=0;i<n;i++) in[i]=false;
	cb = f(pb);
	for(auto i:pb) if(in[i.ind]==false) ccb.push_back(i);
	ccb = f(ccb);
	/*
	cout<<"ca --------------\n";
	for(auto i:ca){
		cout<<i.x<<" "<<i.y<<" "<<i.ind<<"\n";
	}
	cout<<"cb --------------\n";
	for(auto i:cb){
		cout<<i.x<<" "<<i.y<<" "<<i.ind<<"\n";
	}
	cout<<"cca --------------\n";
	for(auto i:cca){
		cout<<i.x<<" "<<i.y<<" "<<i.ind<<"\n";
	}
	cout<<"ccb --------------\n";
	for(auto i:ccb){
		cout<<i.x<<" "<<i.y<<" "<<i.ind<<"\n";
	}
	cout<<"end of debug-----\n";
	*/
	
}
int get(vector<Point> &v,long long X, long long Y){

	int l=0,r=v.size()-2,ret=v.size()-2;
	while(l<r){
		int mid = (l+r)/2;
		long long y=pa[mid+1].y-pa[mid].y, x=pa[mid+1].x-pa[mid].x;
		if(y*X<(-Y)*x){
			ret = min(ret, mid);
			r=mid-1;
		}
		else l=mid+1;
	}
	return ret;
}
long long BestSquad(int X, int Y){
	
	int ica = get(ca,X,Y),icb=get(cb,X,Y),icca=get(cca,X,Y),iccb=get(ccb,X,Y);
	vector<Point> at,df;
	for(int i=-1;i<=1;i++) if(0<=ica+i&&ica+i<ca.size()) at.push_back(ca[ica+i]);
	for(int i=-1;i<=1;i++) if(0<=icca+i&&icca+i<cca.size()) at.push_back(cca[icca+i]);
	for(int i=-1;i<=1;i++) if(0<=icb+i&&icb+i<cb.size()) df.push_back(cb[ica+i]);
	for(int i=-1;i<=1;i++) if(0<=iccb+i&&iccb+i<ccb.size()) df.push_back(ccb[icca+i]);
	long long ret=0;
	for(auto i:at){
		for(auto j:df){
			if(i.ind!=j.ind){
				long long t = (i.x+j.x)*X+(i.y+j.y)*Y;
				//cout<<"check "<<aa<<" "<<bb<<" "<<t<<"\n";
				if(ret<t) ret=t;
			}
		}
	}
	return ret;
}

컴파일 시 표준 에러 (stderr) 메시지

squad.cpp: In function 'long long int BestSquad(int, int)':
squad.cpp:91:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=-1;i<=1;i++) if(0<=ica+i&&ica+i<ca.size()) at.push_back(ca[ica+i]);
                                      ~~~~~^~~~~~~~~~
squad.cpp:92:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=-1;i<=1;i++) if(0<=icca+i&&icca+i<cca.size()) at.push_back(cca[icca+i]);
                                       ~~~~~~^~~~~~~~~~~
squad.cpp:93:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=-1;i<=1;i++) if(0<=icb+i&&icb+i<cb.size()) df.push_back(cb[ica+i]);
                                      ~~~~~^~~~~~~~~~
squad.cpp:94:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=-1;i<=1;i++) if(0<=iccb+i&&iccb+i<ccb.size()) df.push_back(ccb[icca+i]);
                                       ~~~~~~^~~~~~~~~~~

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