QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#50351 | #862. Social Justice | SGColin | WA | 4ms | 3720kb | C++17 | 1.5kb | 2022-09-25 15:30:24 | 2022-09-25 15:30:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int rd() {
int x = 0;
bool f = false;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}
#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define N 200007
int pos[N];
pair<int, int> a[N];
ll p, q, sum[N];
vector<int> res;
inline bool check(int l, int r) {
return (sum[r] - sum[l]) * p >= (r - l) * q * a[r].fr;
}
inline void work() {
int n = rd();
for (int i = 1; i <= n; ++i) {
a[i].fr = rd(); a[i].sc = i;
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + a[i].fr;
p = rd(), q = rd();
int r = 1;
while (r < n && check(0, r + 1)) ++r;
pos[0] = r;
int ans = n - r;
for (int l = 1; l < n; ++l) {
while (r < n && check(l, r + 1)) ++r;
pos[l] = r;
ans = min(ans, n - r + l);
}
int L = n, R = 0;
for (int l = 0; l < n; ++l)
if (n - pos[l] + l == ans) {
L = min(L, l);
R = max(R, pos[l]);
}
while (a[L].fr == a[L + 1].fr) --L;
++R;
while (a[R].fr == a[R - 1].fr) ++R;
printf("%d\n", L + n - R + 1);
res.clear();
for (int i = 1; i <= L; ++i) res.pb(a[i].sc);
for (int i = R; i <= n; ++i) res.pb(a[i].sc);
sort(all(res));
for (auto x : res) printf("%d ", x);
puts("");
}
int main() {
for (int t = rd(); t; --t) work();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3720kb
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: 4ms
memory: 3568kb
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 0 1 12 0 10 1 4 5 6 7 13 14 15 18 20 1 16 1 18 1 13 10 4 5 6 9 11 15 16 18 19 20 0 0 1 10 0 10 1 2 4 6 8 9 11 13 18 20...
result:
wrong answer 69th numbers differ - expected: '2', found: '0'