QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#608085 | #9427. Collect the Coins | 2497201210 | WA | 2ms | 3536kb | C++20 | 1.6kb | 2024-10-03 18:24:11 | 2024-10-03 18:24:15 |
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;
}
}
}
}
}
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'