QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#874487 | #862. Social Justice | asdfsdf# | WA | 2ms | 7908kb | C++23 | 1.6kb | 2025-01-28 08:07:44 | 2025-01-28 08:07:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define MAX 303030
#define MOD 1'000'000'007
int A[MAX];
int loc[MAX];
ll S[MAX];
int chk[MAX];
int ans[MAX];
void solve() {
int N;
cin >> N;
ll P, Q;
int i, a;
vector<pii> in;
for (i = 1; i <= N; i++) chk[i] = ans[i] = 0;
for (i = 1; i <= N; i++) {
cin >> a;
in.emplace_back(a, i);
}
cin >> P >> Q;
sort(in.begin(), in.end());
for (i = 1; i <= N; i++) {
A[i] = in[i - 1].first;
loc[i] = in[i - 1].second;
S[i] = S[i - 1] + A[i];
}
int l, r;
l = 1;
r = N + 1;
while (r - l > 1) {
int m = l + r >> 1;
int chk = 0;
for (i = m; i <= N; i++) {
ll s = S[i] - S[i - m];
if (s * P >= Q * m * A[i]) {
chk = 1;
break;
}
}
if (chk) l = m;
else r = m;
}
ll mx = -1;
for (i = l; i <= N; i++) {
ll s = S[i] - S[i - l];
if (s * P >= Q * l * A[i]) chk[i - l + 1] = 1;
}
int lv = -N - 1557;
for (i = 1; i <= N; i++) {
if (chk[i]) lv = i;
if (i - lv < l) ans[i] = 1;
}
ll mn = 2e9;
for (i = N - l; i >= 1; i--) {
ll a = A[i + l];
ll s = A[i + l] - A[i + 1];
ll x = a * l * Q - P * s;
x = (x + P - 1) / P;
mn = min(mn, x);
if (mn <= A[i]) ans[i] = 1;
}
vector<int> ansv;
for (i = 1; i <= N; i++) if (!ans[i]) ansv.push_back(loc[i]);
sort(ansv.begin(), ansv.end());
cout << ansv.size() << '\n';
for (auto v : ansv) cout << v << ' ';
cout << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int T;
cin >> T;
while (T--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5736kb
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: 2ms
memory: 7908kb
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 1 5 3 2 4 6 6 2 4 6 12 14 16 8 2 4 6 12 14 16 22 24 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 18 19 20 0 2 2 8 2 9 12 2 2 14 10 1 4 5 6 7 13 14 15 18 20 2 9 16 2 16 18 2 5 13 10 4 5 6 9 11 15 16 18 19 20 2 5 19 2 5 13 2 10 15...
result:
wrong answer 470th numbers differ - expected: '9', found: '10'