QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#607707 | #9427. Collect the Coins | ucup-team4435# | TL | 43ms | 4288kb | C++20 | 2.9kb | 2024-10-03 15:53:40 | 2024-10-03 15:53:41 |
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;
while (R - L > 1) {
int v = (L + R) / 2;
vector<pair<ll, ll>> pts(n);
rep(i, n) {
pts[i].first = t[i] * v + c[i];
pts[i].second = t[i] * v - c[i];
}
sort(all(pts));
ll x = -INF, y = -INF;
bool ok = true;
for(auto &[_, val] : pts) {
if (val >= x) {
x = val;
continue;
}
if (val >= y) {
y = val;
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: 3564kb
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: 0
Accepted
time: 43ms
memory: 4288kb
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:
ok 1135 lines
Test #3:
score: -100
Time Limit Exceeded
input:
1 1000000 2 57841 2 357142 3 496329 3 545446 4 503408 4 590762 5 78281 6 196926 6 349414 7 200245 8 953412 11 616898 12 592065 13 945945 15 20908 15 852722 16 221184 16 401521 17 884478 18 186072 18 931445 19 833560 20 314177 21 138453 21 731965 22 172104 23 595921 25 372617 27 545759 28 977029 30 4...