QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#608097#9427. Collect the Coins2497201210TL 905ms167320kbC++201.6kb2024-10-03 18:28:422024-10-03 18:28:42

Judging History

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

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

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){
				
				l=min(l,d-cha);
				r=max(r,d+cha);d=pos;
			}
			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;
				}
			}
		}
	}
	return 1;
}
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: 100
Accepted
time: 0ms
memory: 3612kb

input:

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

output:

2
0
-1

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 53ms
memory: 5240kb

input:

1135
2
6 5
8 8
8
2 9
2 10
4 4
5 3
6 2
6 8
8 2
8 7
1
9 1
6
4 6
6 1
6 2
9 10
10 1
10 7
5
1 6
2 5
6 7
8 6
10 3
8
1 10
5 4
5 7
6 1
6 6
8 4
9 1
9 4
8
1 1
1 3
2 9
3 3
5 9
6 10
9 7
10 7
3
5 8
6 6
10 6
7
2 9
4 7
5 10
6 3
6 7
8 9
10 1
6
1 4
2 8
5 9
7 10
9 1
10 5
9
2 7
4 5
5 9
6 10
7 4
9 4
9 9
10 3
10 7
1
3 1...

output:

0
3
0
3
1
3
6
0
3
2
2
0
2
5
0
1
5
1
2
0
0
0
1
4
2
0
2
1
3
0
3
2
3
2
5
3
1
1
0
1
1
1
0
2
0
1
0
1
0
2
1
0
2
3
4
4
1
1
1
0
1
3
0
1
4
4
3
0
0
2
2
6
4
2
1
0
0
1
0
2
1
2
0
1
1
3
0
0
1
2
0
3
0
2
2
2
1
0
0
0
5
1
2
0
6
1
1
1
2
2
2
0
3
1
4
3
6
0
8
1
1
3
0
2
2
4
1
1
0
0
0
7
2
2
1
0
0
3
1
2
1
1
2
5
3
0
3
3
3
5
...

result:

ok 1135 lines

Test #3:

score: 0
Accepted
time: 819ms
memory: 122432kb

input:

1
1000000
2 57841
2 357142
3 496329
3 545446
4 503408
4 590762
5 78281
6 196926
6 349414
7 200245
8 953412
11 616898
12 592065
13 945945
15 20908
15 852722
16 221184
16 401521
17 884478
18 186072
18 931445
19 833560
20 314177
21 138453
21 731965
22 172104
23 595921
25 372617
27 545759
28 977029
30 4...

output:

994024

result:

ok single line: '994024'

Test #4:

score: 0
Accepted
time: 905ms
memory: 167320kb

input:

1
1000000
6 1991827
13 8125243
19 22493
24 4282711
28 356362
39 765152
41 6737899
44 8549464
57 4530192
64 7201376
67 6695629
70 3830504
70 6658581
71 4591382
71 8349070
75 2107828
76 4073563
81 2712838
92 1391185
95 4663781
102 5986957
113 8423636
118 7826607
122 1171556
122 3118750
160 938066
162 ...

output:

9609125

result:

ok single line: '9609125'

Test #5:

score: -100
Time Limit Exceeded

input:

1
1000000
108 565196036
597 561009880
1007 831705109
2597 55966094
2869 765993518
3025 202191673
3283 237167825
3410 829643653
4879 960747182
7284 679152790
8765 64201585
8899 97619554
9320 713144607
9519 991746776
9913 346063307
11161 970513525
11256 975123550
12073 778562963
14286 206857559
15803 ...

output:

268764694

result: