QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#608103 | #9427. Collect the Coins | 2497201210 | WA | 43ms | 4840kb | C++20 | 1.6kb | 2024-10-03 18:32:10 | 2024-10-03 18:32:10 |
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;
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() {
int n;
cin>>n;
bool f=1;idx=0;
for(int i=1; i<=n; i++) {
int a,b;
cin>>a>>b;
if(md[idx].first!=a){
md[++idx].first=a;
md[idx].second.push_back(b);
}
else{
md[idx].second.push_back(b);
}
if(md[idx].second.size()>2)f=0;
}
if(f) {
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: 3636kb
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: 43ms
memory: 4840kb
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 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -...
result:
wrong answer 2nd lines differ - expected: '3', found: '-1'