QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#54280 | #862. Social Justice | ckiseki# | WA | 5ms | 3724kb | C++ | 2.4kb | 2022-10-07 19:02:53 | 2022-10-07 19:02:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int64_t cdiv(int64_t a, int64_t b) {
return (a + b - 1) / b;
}
signed main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int64_t> a(n);
vector<int64_t> pre(n + 1);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int i, int j) { return a[i] < a[j]; });
int p, q;
cin >> p >> q; // K = p / q
sort(a.begin(), a.end());
for (int i = 0; i < n; i++)
pre[i + 1] = pre[i] + a[i];
const auto ok = [&](int l, int r) {
// using llf = long double;
const int ret = a[r - 1] * q * (r - l) <= p * (pre[r] - pre[l]);
// cerr << a[r-1] << "<=" << (pre[r]-pre[l])/llf(r-l)*p/q << ' ' << ret << endl;
return ret;
};
vector<int> left(n);
int ans = 0;
for (int i = 0; i < n; i++) {
int l = i;
for (int s = 1<<20; s; s >>= 1) {
if (l - s >= 0 && ok(l - s, i + 1)) {
l -= s;
}
}
left[i] = l;
ans = max(ans, i + 1 - l);
}
vector<int> sum(n + 1);
for (int i = 0; i < n; i++) {
if (i + 1 - left[i] != ans) continue;
// a[i] <= (sum - a[left[i]] + a[x]) / ans * K
// a[x] >= ceil(a[i] * ans / K) - (sum - a[left[i]])
// x < left[i];
int64_t U = cdiv(a[i] * ans * q, p) - (pre[i + 1] - pre[left[i] + 1]);
int j = lower_bound(a.begin(), a.begin() + left[i], U) - a.begin();
int k = upper_bound(a.begin(), a.end(), a[i]) - a.begin();
sum[j] += 1;
sum[k] -= 1;
}
for (int i = 1; i < n; i++)
sum[i] += sum[i - 1];
vector<int> res;
for (int i = 0; i < n; i++)
if (sum[i] == 0)
res.push_back(id[i]+1);
cout << res.size() << '\n';
for (size_t i = 0; i < res.size(); i++) {
cout << res[i];
if (i + 1 != res.size())
cout << ' ';
}
cout << '\n';
// cerr << "max = " << ans << endl;
// for (int i = 0; i < n; i++) {
// cerr << left[i] << ',';
// }
// cerr << endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3624kb
input:
3 4 1 2 3 4 3 2 5 1 15 2 5 1 2 1 5 1 2 3 1000 10000 4 3
output:
0 1 2 2 4 5
result:
ok 6 numbers
Test #2:
score: -100
Wrong Answer
time: 5ms
memory: 3724kb
input:
1000 1 10 3 2 2 10 100 3 2 3 10 10 100 3 2 4 1 2 3 4 3 2 5 1 15 2 5 1 2 1 5 1 2 3 1000 10000 4 3 6 1 2 3 4 1000 10000 4 3 5 50000 2 1 1 5000 2 1 10 1 15 2 5 1 10000 1 1 1 1 2 1 20 1 15 2 5 1 10000 1 1 1 1 1 15 2 5 1 10000 1 1 1 1 2 1 25 1 15 2 5 1 10000 1 1 1 1 1 15 2 5 1 10000 1 1 1 1 1 15 2 5 1 2 ...
output:
0 0 1 3 0 1 2 2 4 5 3 1 5 6 2 5 1 3 4 2 6 6 14 4 12 2 6 16 8 14 4 24 12 22 2 16 6 13 1 2 3 4 5 6 7 8 9 10 11 12 20 15 1 2 3 4 5 6 7 8 9 10 11 12 20 19 18 0 2 2 8 2 12 9 2 2 14 10 4 5 6 7 18 1 15 13 14 20 2 16 9 2 18 16 2 13 5 10 11 20 19 18 15 9 6 5 4 16 2 19 5 2 13 5 2 10 15 2 14 17 10 11 20 18...
result:
wrong answer 16th numbers differ - expected: '1', found: '5'