QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#607853#9427. Collect the Coins2497201210WA 184ms5704kbC++206.3kb2024-10-03 16:44:592024-10-03 16:45:00

Judging History

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

  • [2024-11-06 15:56:27]
  • hack成功，自动添加数据
  • (/hack/1139)
  • [2024-10-03 16:45:00]
  • 评测
  • 测评结果：WA
  • 用时：184ms
  • 内存：5704kb
查看
  • [2024-10-03 16:44:59]
  • 提交

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) {
	set<int>yy;
	bool g=1;
	if(md[1].second.size()==1) {
		yy.insert(md[1].second[0]);
		for(int i=2; i<=idx; i++) {
			int cha=md[i].first-md[i-1].first;
			cha=cha*x;
			if(md[i].second.size()==1) {
				if(md[i-1].second.size()==1) {
					if(abs(md[i-1].second[0]-md[i].second[0])>cha) {
						bool ff=0;
						if(g)ff=1;
						else {
							auto it=yy.lower_bound(md[i].second[0]);
							if(abs(*it-md[i].second[0])<=cha)ff=1;
							else {
								if(it!=yy.begin()) {
									it=prev(it);
									if(abs(*it-md[i].second[0])<=cha)ff=1;
								}
							}
						}
						if(ff==0)return 0;
						yy.clear();
						yy.insert(md[i].second[0]);
						yy.insert(md[i-1].second[0]);
					} else {
						yy.insert(md[i].second[0]);
					}
				} else {
					if(abs(md[i-1].second[0]-md[i].second[0])<=cha&&abs(md[i-1].second[1]-md[i].second[0])<=cha) {
						yy.insert(md[i].second[0]);
					} else if(abs(md[i-1].second[0]-md[i].second[0])>cha&&abs(md[i-1].second[1]-md[i].second[0])>cha) {
						return 0;
					} else if(abs(md[i-1].second[0]-md[i].second[0])>cha) {
						yy.clear();
						yy.insert(md[i].second[0]);
						yy.insert(md[i-1].second[1]);
					} else {
						yy.clear();
						yy.insert(md[i].second[0]);
						yy.insert(md[i-1].second[0]);
					}
				}
			} else {
				if(abs(md[i-1].second[0]-md[i].second[0])>cha&&abs(md[i-1].second[0]-md[i].second[1])>cha) {
					return 0;
				} else if(abs(md[i-1].second[0]-md[i].second[0])>cha) {
					bool ff=0;
					if(g)ff=1;
					else {
						auto it=yy.lower_bound(md[i].second[0]);
						if(abs(*it-md[i].second[0])<=cha)ff=1;
						else {
							if(it!=yy.begin()) {
								it=prev(it);
								if(abs(*it-md[i].second[0])<=cha)ff=1;
							}
						}
					}
					if(ff==0)return 0;
				}
				else if(abs(md[i-1].second[0]-md[i].second[1])>cha){
					bool ff=0;
					if(g)ff=1;
					else {
						auto it=yy.lower_bound(md[i].second[1]);
						if(abs(*it-md[i].second[1])<=cha)ff=1;
						else {
							if(it!=yy.begin()) {
								it=prev(it);
								if(abs(*it-md[i].second[1])<=cha)ff=1;
							}
						}
					}
					if(ff==0)return 0;
				}
				else{
					bool ff=0;
					if(g)ff=1;
					else {
						auto it=yy.lower_bound(md[i].second[0]);
						if(abs(*it-md[i].second[0])<=cha)ff=1;
						else {
							if(it!=yy.begin()) {
								it=prev(it);
								if(abs(*it-md[i].second[0])<=cha)ff=1;
							}
						}
						it=yy.lower_bound(md[i].second[1]);
						if(abs(*it-md[i].second[1])<=cha)ff=1;
						else {
							if(it!=yy.begin()) {
								it=prev(it);
								if(abs(*it-md[i].second[1])<=cha)ff=1;
							}
						}
					}
					if(ff==0)return 0;
				}
				yy.clear();
				yy.insert(md[i].second[0]);
				yy.insert(md[i].second[1]);
			}
		}
	}
	else{
		g=0;
		yy.insert(md[1].second[0]);yy.insert(md[1].second[1]);
		for(int i=2; i<=idx; i++) {
			int cha=md[i].first-md[i-1].first;
			cha=cha*x;
			if(md[i].second.size()==1) {
				if(md[i-1].second.size()==1) {
					if(abs(md[i-1].second[0]-md[i].second[0])>cha) {
						bool ff=0;
						if(g)ff=1;
						else {
							auto it=yy.lower_bound(md[i].second[0]);
							if(abs(*it-md[i].second[0])<=cha)ff=1;
							else {
								if(it!=yy.begin()) {
									it=prev(it);
									if(abs(*it-md[i].second[0])<=cha)ff=1;
								}
							}
						}
						if(ff==0)return 0;
						yy.clear();
						yy.insert(md[i].second[0]);
						yy.insert(md[i-1].second[0]);
					} else {
						yy.insert(md[i].second[0]);
					}
				} else {
					if(abs(md[i-1].second[0]-md[i].second[0])<=cha&&abs(md[i-1].second[1]-md[i].second[0])<=cha) {
						yy.insert(md[i].second[0]);
					} else if(abs(md[i-1].second[0]-md[i].second[0])>cha&&abs(md[i-1].second[1]-md[i].second[0])>cha) {
						return 0;
					} else if(abs(md[i-1].second[0]-md[i].second[0])>cha) {
						yy.clear();
						yy.insert(md[i].second[0]);
						yy.insert(md[i-1].second[1]);
					} else {
						yy.clear();
						yy.insert(md[i].second[0]);
						yy.insert(md[i-1].second[0]);
					}
				}
			} else {
				if(abs(md[i-1].second[0]-md[i].second[0])>cha&&abs(md[i-1].second[0]-md[i].second[1])>cha) {
					return 0;
				} else if(abs(md[i-1].second[0]-md[i].second[0])>cha) {
					bool ff=0;
					if(g)ff=1;
					else {
						auto it=yy.lower_bound(md[i].second[0]);
						if(abs(*it-md[i].second[0])<=cha)ff=1;
						else {
							if(it!=yy.begin()) {
								it=prev(it);
								if(abs(*it-md[i].second[0])<=cha)ff=1;
							}
						}
					}
					if(ff==0)return 0;
				}
				else if(abs(md[i-1].second[0]-md[i].second[1])>cha){
					bool ff=0;
					if(g)ff=1;
					else {
						auto it=yy.lower_bound(md[i].second[1]);
						if(abs(*it-md[i].second[1])<=cha)ff=1;
						else {
							if(it!=yy.begin()) {
								it=prev(it);
								if(abs(*it-md[i].second[1])<=cha)ff=1;
							}
						}
					}
					if(ff==0)return 0;
				}
				else{
					bool ff=0;
					if(g)ff=1;
					else {
						auto it=yy.lower_bound(md[i].second[0]);
						if(abs(*it-md[i].second[0])<=cha)ff=1;
						else {
							if(it!=yy.begin()) {
								it=prev(it);
								if(abs(*it-md[i].second[0])<=cha)ff=1;
							}
						}
						it=yy.lower_bound(md[i].second[1]);
						if(abs(*it-md[i].second[1])<=cha)ff=1;
						else {
							if(it!=yy.begin()) {
								it=prev(it);
								if(abs(*it-md[i].second[1])<=cha)ff=1;
							}
						}
					}
					if(ff==0)return 0;
				}
				yy.clear();
				yy.insert(md[i].second[0]);
				yy.insert(md[i].second[1]);
			}
		}
	}
	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();
	}
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3860kb

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: -100
Wrong Answer
time: 184ms
memory: 5704kb

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
0
2
6
0
3
0
1
0
2
5
0
1
5
1
1
0
0
0
1
4
2
0
3
0
3
0
1
2
3
2
5
2
1
0
0
1
1
1
0
1
0
1
0
0
0
2
0
0
1
0
4
2
0
1
0
0
0
3
0
1
3
3
3
0
0
1
2
6
4
1
0
0
0
0
0
2
1
0
0
0
1
3
0
0
0
0
0
3
0
1
2
1
0
0
0
0
5
0
0
0
6
1
0
0
2
2
0
0
3
0
0
2
6
0
8
0
0
3
0
2
2
4
0
0
0
0
0
7
2
1
0
0
0
3
1
2
0
2
2
5
3
0
3
3
3
4
...

result:

wrong answer 5th lines differ - expected: '1', found: '0'
English 繁體中文 简体中文

Server Time: 2024-12-05 06:26:03 | OpenSource Project