QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#607853 | #9427. Collect the Coins | 2497201210 | WA | 184ms | 5704kb | C++20 | 6.3kb | 2024-10-03 16:44:59 | 2024-10-03 16:45:00 |
Judging History
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();
}
}
详细
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'