QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#607717 | #9427. Collect the Coins | ucup-team4435# | WA | 22ms | 4284kb | C++20 | 3.0kb | 2024-10-03 15:57:34 | 2024-10-03 15:57:35 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define each(x, a) for (auto &x : a)
#define ar array
#define vec vector
#define range(i, n) rep(i, n)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;
int Bit(int mask, int b) { return (mask >> b) & 1; }
template<class T>
bool ckmin(T &a, const T &b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<class T>
bool ckmax(T &a, const T &b) {
if (b > a) {
a = b;
return true;
}
return false;
}
// [l, r)
template<typename T, typename F>
T FindFirstTrue(T l, T r, const F &predicat) {
--l;
while (r - l > 1) {
T mid = l + (r - l) / 2;
if (predicat(mid)) {
r = mid;
} else {
l = mid;
}
}
return r;
}
template<typename T, typename F>
T FindLastFalse(T l, T r, const F &predicat) {
return FindFirstTrue(l, r, predicat) - 1;
}
const ll INF = 2e18;
const int INFi = 1e9;
const int N = 30 + 5;
const int LG = 20;
void solve() {
int n; cin >> n;
vl t(n), c(n);
rep(i, n) cin >> t[i] >> c[i];
for(int i = 1; i + 1 < n; ++i) {
if (t[i - 1] == t[i] && t[i] == t[i + 1]) {
cout << "-1\n";
return;
}
}
if (set<int>(all(c)).size() <= 2) {
cout << "0\n";
return;
}
int L = 0;
int R = (int)1e9 + 1;
vector<pair<ll, ll>> pts(n);
while (R - L > 1) {
int v = (L + R) / 2;
rep(i, n) {
pts[i].first = t[i] * v + c[i];
pts[i].second = t[i] * v - c[i];
}
pair<ll, ll> a = {-INF, -INF}, b = {-INF, -INF};
bool ok = true;
for(auto &[cx, cy] : pts) {
if (a.first <= cx && a.second <= cy) {
a = {cx, cy};
continue;
}
if (b.first <= cx && b.second <= cy) {
b = {cx, cy};
swap(a, b);
continue;
}
ok = false;
break;
}
if (ok) {
R = v;
} else {
L = v;
}
}
cout << R << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout << setprecision(12) << fixed;
int t = 1;
cin >> t;
rep(i, t) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3488kb
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: 22ms
memory: 4284kb
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'