求 Hack
查看原帖
求 Hack
515129
TLEWA楼主2023/11/25 13:50

rt

#include<bits/stdc++.h>

using namespace std;

const int N=200005,A=1000005,INF=1e8;

int T;
int n;

vector<pair<int,int> > vec[A],que[A];
set<int> input_list;

struct Node {
	int a,b,m;
}inputs[N];

int main() {
	cin >> T;
	while(T--) {
		cin >> n;
		
		input_list.clear();
		
		int a,b,m;
		for(int i=1;i<=n;++i) {
			cin >> a >> b >> m;
			if(!vec[a+b-m].empty() && input_list.find(a+b-m)==input_list.end()) {
				vec[a+b-m].clear();que[a+b-m].clear();
			}
			vec[a+b-m].push_back(make_pair(a-m,a-max(0,m-b)));
			input_list.insert(a+b-m);
			inputs[i]={a,b,m};
		}
		
		int ans=0,rmax=0;
		
		for(auto now:input_list) {
			sort(vec[now].begin(),vec[now].end());
			
			rmax=INF,ans++;
			for(auto u:vec[now]) {
				if(u.first>rmax) {
					que[now].push_back(make_pair(u.first-1,rmax));
					rmax=u.second,ans++;
				}
				else rmax=min(rmax,u.second);
			}
			que[now].push_back(make_pair(INF,rmax));
		}
		
		cout << ans << endl;
		
		for(int i=1;i<=n;++i) {
			a=inputs[i].a,b=inputs[i].b,m=inputs[i].m;
			auto p=*(upper_bound(que[a+b-m].begin(),que[a+b-m].end(),make_pair(a+b-m,-INF)));
			if((a-p.second)<=a && m-(a-p.second)<=b && (a-p.second)>=0 && m-(a-p.second)>=0) cout << (a-p.second) << ' ' << m-(a-p.second) << endl;
			else cout << min(m,a) << ' ' << m-min(m,a) << endl;
		}
	}
	return 0;
}
2023/11/25 13:50
加载中...