QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#607795 | #9427. Collect the Coins | SGColin | WA | 9ms | 5936kb | C++20 | 1.5kb | 2024-10-03 16:24:06 | 2024-10-03 16:24:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;
#define eb emplace_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}
const int N = 1000007;
const ll inf = 1000000000000000000ll;
int c[N], t[N];
inline void work() {
int n = rd();
bool fl = false;
rep(i, 1, n) {
t[i] = rd(); c[i] = rd();
if (i > 2 && t[i - 2] == t[i]) fl = true;
}
if (fl) {puts("-1"); return;}
auto check = [&](ll spd) {
ll L = -inf, R = inf;
rep(i, 2, n) {
ll D = spd * (t[i] - t[i - 1]);
if (abs(c[i] - c[i - 1]) > D) {
if (c[i] < L - D || c[i] > R + D) return false;
L = R = c[i - 1];
}
L -= D; L = max(L, -inf);
R += D; R = min(R, inf);
}
return true;
};
int L = 0, R = 1000000000;
while (L < R) {
int m = (L + R) / 2;
check(m) ? R = m : L = m + 1;
}
printf("%d\n", L);
}
int main() {
per(t, rd(), 1) work();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5888kb
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: 9ms
memory: 5936kb
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 6 1 2 0 0 0 1 4 4 0 2 1 3 0 3 2 3 2 5 4 1 1 0 1 1 1 0 3 0 1 0 1 0 2 1 0 2 3 4 7 1 1 1 0 1 3 0 1 4 4 4 0 0 2 2 6 4 3 1 0 0 1 0 2 1 2 0 1 5 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 8 3 0 3 3 3 5 ...
result:
wrong answer 17th lines differ - expected: '5', found: '6'