QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#625830 | #9427. Collect the Coins | nhat2004 | WA | 44ms | 3708kb | C++20 | 1.5kb | 2024-10-09 21:18:23 | 2024-10-09 21:18:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct coin1{
int timer,pos;
};
int n;
coin1 coin[1000006];
int check(int k){
pair<int,int> robot[2];
robot[0].first = 0;
robot[0].second = 0;
robot[1].first = 0;
robot[1].second = 0;
for (int i = 1;i<=n;i++){
if (robot[0].first == 0){
robot[0].second = coin[i].timer;
robot[0].first = coin[i].pos;
}else if ((robot[0].first + (coin[i].timer-robot[0].second)*k >= coin[i].pos) && (robot[0].first - (coin[i].timer-robot[0].second)*k <= coin[i].pos)){
robot[0].first = coin[i].pos;
robot[0].second = coin[i].timer;
}else if (robot[1].first==0){
robot[1].first = coin[i].pos;
robot[1].second = coin[i].timer;
}else if ((robot[1].first + (coin[i].timer-robot[1].second)*k)>=coin[i].pos && (robot[1].first - (coin[i].timer-robot[1].second)*k)<=coin[i].pos){
robot[1].first = coin[i].pos;
robot[1].second = coin[i].timer;
}else return 0;
}
return 1;
}
signed main(){
int tc;
cin >> tc;
while(tc--){
cin >> n ;
for (int i = 1;i<=n;i++){
cin >> coin[i].timer >> coin[i].pos;
}
int l = 0,r = 1e9,res=-1,cnt= 0;
while(l<=r){
int mid = (l+r)/2;
if (check(mid)==1){
res= mid;
r = mid-1;
}else {
l = mid + 1;
}
}
cout << res << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3576kb
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: 44ms
memory: 3708kb
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 3 1 0 0 2 0 3 1 2 0 1 1 3 0 0 1 2 0 3 0 2 2 2 1 0 0 0 5 2 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 74th lines differ - expected: '2', found: '3'