QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#251044 | #862. Social Justice | thomas_li# | WA | 0ms | 7568kb | C++17 | 2.2kb | 2023-11-14 07:00:50 | 2023-11-14 07:00:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define cmx(x,y) x = max(x,y)
#define cmn(x,y) x = min(x,y)
#define ary(k) array<int,k>
typedef pair<int,int> pii;
typedef vector<int> vi;
pii tab[1000002];
int pref[1000002];
int lg[1000002], res[1000002];
void fun() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> tab[i].FS;
tab[i].SD = i;
}
sort(tab+1, tab+n+1);
for (int i = 1; i <= n; i++) {
pref[i] = pref[i-1] + tab[i].FS;
res[i] = 0;
}
int p, q;
cin >> p >> q;
int longest = 0;
for (int i = 1; i <= n; i++) {
int pocz = 1, kon = i;
while (pocz < kon) {
int sr = (pocz + kon) / 2;
int sum = pref[i] - pref[sr - 1];
// tab[i] <= sum / (ile) * (p/q)
if (tab[i].FS * (i - sr + 1) * q <= sum * p) {
kon = sr;
} else {
pocz = sr + 1;
}
}
lg[i] = pocz;
// cerr << i << " " << lg[i] << "\n";
cmx(longest, i - pocz + 1);
}
// cerr << longest << "\n";
for (int i = 1; i <= n; i++) {
if (i - lg[i] + 1 < longest)
continue;
int pocz = 1, kon = lg[i];
while (pocz < kon) {
int sr = (pocz + kon) / 2;
int sum = pref[i] - pref[lg[i] - 1] - tab[lg[i]].FS + tab[sr].FS;
// tab[i] <= sum / (ile) * (p/q)
if (tab[i].FS * (i - sr + 1) * q <= sum * p) {
kon = sr;
} else {
pocz = sr + 1;
}
}
res[pocz]++;
res[i+1]--;
}
vi ans;
for (int i = 1; i <= n; i++) {
res[i] += res[i-1];
if (res[i] == 0)
ans.PB(tab[i].SD);
}
sort(all(ans));
cout << sz(ans) << "\n";
for (auto a : ans) {
cout << a << " ";
}
cout << "\n";
}
signed main(){
cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
int z;
cin >> z;
while (z--) fun();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7476kb
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: 0ms
memory: 7568kb
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'