QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#613643 | #9427. Collect the Coins | Null_Resot | WA | 11ms | 3944kb | C++20 | 1.7kb | 2024-10-05 14:24:10 | 2024-10-05 14:24:15 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
typedef std::pair<long long, long long> PII;
const int mod = 998244353;
const int N = 2e6 + 1000;
const int INF = 0x3f3f3f3f;
const long long LINF = 1e18;
const double eps = 1e-12;
const double pi = std::acos(-1);
std::mt19937_64 rnd(std::random_device{}());
void solve() {
int n;
std::cin >> n;
std::vector<PII> a(n);
for (auto &[t, p] : a) std::cin >> t >> p;
auto check = [&](i64 v) {
i64 l = -INF, r = INF;
i64 pos = 0, last = 0;
for (auto [t, p] : a) {
if (!pos) {
pos = p;
last = t;
continue;
}
i64 w = (t - last) * v;
if ((pos - w <= p && p <= pos + w) && (l - w <= p && p <= r + w)) {
l = std::min(l - w, pos - w);
r = std::max(r + w, pos + w);
} else if (pos - w <= p && p <= pos + w) {
l -= w;
r += w;
} else if (l - w <= p && p <= r + w) {
l = pos - w;
r = pos + w;
} else {
return false;
}
pos = p;
last = t;
}
return true;
};
i64 l = 0, r = 1e18;
while (l < r) {
i64 mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
if (r == 1e18) r = -1;
std::cout << r << "\n";
}
signed main() {
std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
int tmp = 1;
std::cin >> tmp;
while (tmp--)
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3532kb
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: 11ms
memory: 3944kb
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 202nd lines differ - expected: '4', found: '982370986173881453'