QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#608090 | #9427. Collect the Coins | 2497201210 | WA | 54ms | 5348kb | C++20 | 1.6kb | 2024-10-03 18:25:33 | 2024-10-03 18:25:33 |
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) {
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;
}
}
}
}
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: 3596kb
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: 54ms
memory: 5348kb
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:
wrong answer 273rd lines differ - expected: '2', found: '3'