QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#608085#9427. Collect the Coins2497201210WA 2ms3536kbC++201.6kb2024-10-03 18:24:112024-10-03 18:24:15

Judging History

你现在查看的是最新测评结果

  • [2024-11-06 15:56:27]
  • hack成功,自动添加数据
  • (/hack/1139)
  • [2024-10-03 18:24:15]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3536kb
  • [2024-10-03 18:24:11]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=1e6+10;
const int P=1e9+7;
map<int,vector<int>>hh;
pair<int,vector<int>>md[N];
int idx=0;
bool check(int x) {
	int l=-1e10;int r=1e10;
	int d;
	if(md[1].second.size()==1){
		d=md[1].second[0];
	}
	else {
		d=md[1].second[0];
		l=r=md[1].second[1];
	}
	for(int i=2;i<=idx;i++){
		int cha=md[i].first-md[i-1].first;
		cha=cha*x;
		l-=cha;r+=cha;
		if(md[i].second.size()==2){
			int pos1=md[i].second[0];int pos2=md[i].second[1];
			if(pos1>=d-cha&&pos1<=d+cha&&pos2>=l&&pos2<=r){
				d=pos1;
				l=r=pos2;
			}
			else if(pos2>=d-cha&&pos2<=d+cha&&pos1>=l&&pos1<=r){
				d=pos1;
				l=r=pos2;
			}
			else{
				return 0;
			}
		}
		else{
			int pos=md[i].second[0];
			if(pos>=l&&pos<=r&&pos>=d-cha&&pos<=d+cha){
				d=pos;
				l=min(l,d-cha);
				r=max(r,d+cha);
			}
			else{
				if(pos>=l&&pos<=r){
					l=d-cha;
					r=d+cha;
					d=pos;
				}
				else if(pos>=d-cha&&pos<=d+cha){
					d=pos;
				}
				else{
					return 0;
				}
			}
		}
	}
}
inline void solve() {
	hh.clear();
	int n;
	cin>>n;
	bool f=1;
	for(int i=1; i<=n; i++) {
		int a,b;
		cin>>a>>b;
		hh[a].push_back(b);
		if(hh[a].size()>2)f=0;
	}
	if(f) {
		idx=0;
		for(auto&it:hh) {
			md[++idx]= {it.first,it.second};
		}
		int l=0;
		int r=1e9+100;
		while(l<r) {
			int mid=l+r>>1;
			if(check(mid))r=mid;
			else l=mid+1;
		}
		cout<<l<<endl;
	} else {
		cout<<-1<<endl;
	}
}
signed main() {

	cin.tie(0);
	cout.tie(0);
	int t;
	t=1;
	cin>>t;
	while(t--) {
		solve();
	}
}


詳細信息

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 3536kb

input:

3
5
1 1
3 7
3 4
4 3
5 10
1
10 100
3
10 100
10 1000
10 10000

output:

1000000100
1000000100
-1

result:

wrong answer 1st lines differ - expected: '2', found: '1000000100'