自动搬运

查看原文

来自洛谷，原作者为

	AThousandSuns Simultaneous release!

搬运于2025-08-24 22:19:23，当前版本为作者最后更新于2020-06-05 19:37:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

每次操作时二分，判断此时跑到最右的 $x$ 粒子是否在跑到最左的 $y$ 粒子右边。模拟 $k$ 次即可。

由于我相信 $O(nk\log n)$ 不能过，我们要接着优化。

其实就是求个半平面交的事。每次重构半平面交，然后把两边的上半部分分段加起来，在上面判断。

由于直线就那么几条，所以不用每次排序。

时间复杂度 $O(n\log n+nk)$。

然后当我发现评测记录里一大堆 0.9s+ 的时候心态就崩了。

第二天我过来补代码，补着补着发现时限甚至变成了 2s，然后提交记录前几个 1.8s+。看起来就是暴力常数太大然后申请开大时限。

然后开始无 能 狂 怒。是真的无能，由于一些原因当时发不了犇犇和帖子，连博客都不能发。

然而改时限其实很没道理，因为官方题解也说了 $O(nk\log n)$ 可以过，当时也没什么卡常迹象，原则上场上能过的在这里也应该给过。所以我就只能干难受了

拿了个最优解不亏

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=50050,mod=998244353;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
	char ch=getchar();ll x=0,f=0;
	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return f?-x:x;
}
struct line{
	int k,id1,id2;
	ll b;
	bool operator<(const line &l)const{
		if(k!=l.k) return k<l.k;
		return b>l.b;
	}
}lx[maxn],ly[maxn],hx[maxn],hy[maxn],h[maxn*2];
int n,l,k,tx[maxn],vx[maxn],ty[maxn],vy[maxn],tpx,tpy,tot;
inline double interx(line l1,line l2){
	return 1.0*(l1.b-l2.b)/(l2.k-l1.k);
}
line merge(line l1,line l2){
	return (line){l1.k+l2.k,l1.id1,l2.id1,l1.b+l2.b};
} 
int main(){
	n=read();l=read();k=read();
	FOR(i,1,n) tx[i]=read(),vx[i]=read(),lx[i]=(line){vx[i],i,0,-1ll*vx[i]*tx[i]};
	FOR(i,1,n) ty[i]=read(),vy[i]=read(),ly[i]=(line){vy[i],i,0,-1ll*vy[i]*ty[i]};
	sort(lx+1,lx+n+1);sort(ly+1,ly+n+1);
	while(k--){
		tpx=0;
		FOR(i,1,n){
			if(tpx && lx[i].k==hx[tpx].k) continue;
			while(tpx>=2 && interx(lx[i],hx[tpx])<=interx(lx[i],hx[tpx-1])) tpx--;
			hx[++tpx]=lx[i];
		}
		tpy=0;
		FOR(i,1,n){
			if(tpy && ly[i].k==hy[tpy].k) continue;
			while(tpy>=2 && interx(ly[i],hy[tpy])<=interx(ly[i],hy[tpy-1])) tpy--;
			hy[++tpy]=ly[i];
		}
		tot=0;
		int j=1;
		FOR(i,1,tpx){
			double lft=i==1?-1e18:interx(hx[i],hx[i-1]),rig=i==tpx?1e18:interx(hx[i],hx[i+1]);
			while(j<=tpy){
				double L=j==1?-1e18:interx(hy[j],hy[j-1]),R=j==tpy?1e18:interx(hy[j],hy[j+1]);
				if(L>rig) break;
				if(R>=lft) h[++tot]=merge(hx[i],hy[j]);
				if(R>rig) break;
				j++;
			}
		}
		int ans1=0,ans2=0;
		FOR(i,1,tot){
			double lft=i==1?-1e18:interx(h[i],h[i-1]),rig=i==tot?1e18:interx(h[i],h[i+1]);
			double x=1.0*(l-h[i].b)/h[i].k;
			if(x>=lft && x<=rig){
				ans1=h[i].id1;
				ans2=h[i].id2;
				break;
			}
		}
		printf("%d %d\n",ans1,ans2);
		FOR(i,1,n-1) if(lx[i].id1==ans1) swap(lx[i],lx[i+1]);
		FOR(i,1,n-1) if(ly[i].id1==ans2) swap(ly[i],ly[i+1]);
		n--;
	}
}