QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#689077 | #862. Social Justice | wzj33300 | AC ✓ | 213ms | 9124kb | C++23 | 6.3kb | 2024-10-30 15:10:36 | 2024-10-30 15:10:36 |
Judging History
answer
/**
* created : 30.10.2024 08:58:08
* author : wzj33300
*/
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include <algo/debug.h>
#else
#define debug(...) 42
#define assert(...) 42
#endif
using ll = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using db = long double; // or double, if TL is tight
using str = string; // yay python!
// pairs
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
#define mp make_pair
#define fi first
#define se second
// ^ lol this makes everything look weird but I'll try it
template <class T>
using vc = vector<T>;
template <class T, size_t SZ>
using AR = array<T, SZ>;
using vi = vc<int>;
using vb = vc<bool>;
using vl = vc<ll>;
using vd = vc<db>;
using vs = vc<str>;
using vpi = vc<pi>;
using vpl = vc<pl>;
using vpd = vc<pd>;
// vectors
// oops size(x), rbegin(x), rend(x) need C++17
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()
#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 rep_subset(t, s) \
for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define lb lower_bound
#define ub upper_bound
template <class T>
int lwb(vc<T> &a, const T &b) {
return int(lb(all(a), b) - bg(a));
}
template <class T>
int upb(vc<T> &a, const T &b) {
return int(ub(all(a), b) - bg(a));
}
// const int MOD = 998244353; // 1e9+7;
const int Big = 1e9; // not too close to INT_MAX
const ll BIG = 1e18; // not too close to LLONG_MAX
const db PI = acos((db)-1);
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1}; // for every grid problem!!
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
int pct(int x) { return __builtin_popcount(x); }
int pct(u32 x) { return __builtin_popcount(x); }
int pct(ll x) { return __builtin_popcountll(x); }
int pct(u64 x) { return __builtin_popcountll(x); }
int popcnt_mod_2(int x) { return __builtin_parity(x); }
int popcnt_mod_2(u32 x) { return __builtin_parity(x); }
int popcnt_mod_2(ll x) { return __builtin_parityll(x); }
int popcnt_mod_2(u64 x) { return __builtin_parityll(x); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
template <typename T>
T floor(T a, T b) {
return a / b - (a % b && (a ^ b) < 0);
}
template <typename T>
T ceil(T x, T y) {
return floor(x + y - 1, y);
}
template <typename T>
T bmod(T x, T y) {
return x - y * floor(x, y);
}
template <typename T>
pair<T, T> divmod(T x, T y) {
T q = floor(x, y);
return {q, x - q * y};
}
template <class T>
bool ckmin(T &a, const T &b) {
return b < a ? a = b, 1 : 0;
} // set a = min(a,b)
template <class T>
bool ckmax(T &a, const T &b) {
return a < b ? a = b, 1 : 0;
} // set a = max(a,b)
template <class T, class U>
T fstTrue(T lo, T hi, U f) {
++hi;
assert(lo <= hi); // assuming f is increasing
while (lo < hi) { // find first index such that f is true
T mid = lo + (hi - lo) / 2;
f(mid) ? hi = mid : lo = mid + 1;
}
return lo;
}
template <class T, class U>
T lstTrue(T lo, T hi, U f) {
--lo;
assert(lo <= hi); // assuming f is decreasing
while (lo < hi) { // find first index such that f is true
T mid = lo + (hi - lo + 1) / 2;
f(mid) ? lo = mid : hi = mid - 1;
}
return lo;
}
// signed main() {
int main() {
// freopen("ex_d1.in", "r", stdin);
// freopen("my.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vpi aa(n);
for (int i = 0; i < n; i++) cin >> aa[i].first, aa[i].second = i;
int P, Q;
cin >> P >> Q;
sor(aa);
vl a(n + 1);
for (int i = 0; i < n; i++) a[i + 1] = a[i] + aa[i].first;
int minall = Big, minleft = Big, minright = Big;
vpi able;
for (int i = 0; i < n; i++) {
int p = fstTrue(0, n - i - 1, [&](int x) {
int l = x, r = n - i;
ll s = a[r] - a[l];
ll mx = a[r] - a[r - 1];
// debug(l, r, s, mx, P, Q);
if (s * P >= mx * Q * (r - l)) {
return true;
} else {
return false;
}
});
// debug(i, p);
if (p == n - i) {
continue;
}
int cnt = i + p;
if (cnt > minall) continue;
if (true) {
int change = p + 1;
int p2 = fstTrue(1, p, [&](int x) {
int l = p, r = n - i;
ll s = a[r] - a[l] + (a[x] - a[x - 1]) - (a[change] - a[change - 1]);
ll mx = a[r] - a[r - 1];
if (s * P >= mx * Q * (r - l)) {
return true;
} else {
return false;
}
});
p = p2 - 1;
}
if (cnt == minall) {
// ckmin(minleft, p);
// ckmin(minright, i);
able.eb(p, n - i);
}
if (cnt < minall) {
minall = cnt;
able.clear();
able.eb(p, n - i);
}
}
debug(minall, minleft, minright);
// if (n == 10) cout << minall << '\n';
// cout << minleft + minright << '\n';
vi dif(n + 1);
for (auto &it : able) dif[it.first]++, dif[it.second]--;
for (int i = 1; i < n; i++) dif[i] += dif[i - 1];
vi ans;
for (int i = 0; i < n; i++)
if (!dif[i]) ans.eb(aa[i].second + 1);
sor(ans);
cout << sz(ans) << '\n';
for (auto &x : ans) cout << x << ' ';
cout << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3864kb
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: 0
Accepted
time: 2ms
memory: 3572kb
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:
ok 6086 numbers
Test #3:
score: 0
Accepted
time: 102ms
memory: 3920kb
input:
125 5000 1 1 1 1000000000 1000000000 1000000000 1000000000 1 1 1 1 1 1000000000 1 1 1 1 1 1 1000000000 1000000000 1 1000000000 1000000000 1000000000 1 1000000000 1000000000 1000000000 1 1 1000000000 1000000000 1 1000000000 1 1 1 1000000000 1000000000 1000000000 1000000000 1000000000 1 1 1 1000000000...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4491 3 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 25 26 27 28 29 30 31 32 33 34 35 36 37 39 40 42 43 44 45 46 48 49 50 51 53 54 55 56 57 58 59 62 63 64 66 67 68 70 71 72 74 75 76 77 78 79 80 81 82 83 84 85 87 88 89 90 93 94 95 96 97 ...
result:
ok 242748 numbers
Test #4:
score: 0
Accepted
time: 182ms
memory: 9124kb
input:
5 200000 512314734 33319999 85503340 443544695 92411616 149252701 723302421 176149500 143875507 972078271 907672089 585808794 390600756 700244129 848509047 550288071 859158053 356354007 437419096 572862734 118863313 959486458 472657137 107261032 199102866 190553436 489624108 79203044 147746132 47881...
output:
181062 1 2 3 4 5 6 7 8 9 12 13 14 15 16 17 18 19 20 21 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 42 43 44 45 46 47 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 79 80 81 82 83 84 85 86 87 88 89 90 91 92 94 95 96 98 99 100 101 102 103 104 105 106 1...
result:
ok 380173 numbers
Test #5:
score: 0
Accepted
time: 213ms
memory: 8856kb
input:
5 200000 15187692 56 41 5053827 3148366 6530 10 131 4381 380972680 499497 8727 371 555036936 2810792 641 3116415 4514225 22284 542730997 129 2227 173361 49408 4 528 1 2660 20568 466863 1 5348 206792 6 150 37 576581 240275683 318 24664 99 34829 38855 177 18018 189646 653 437641 2 219866 5294 3476 856...
output:
83879 2 3 7 8 9 13 16 21 22 25 26 27 28 31 34 35 36 39 41 44 47 49 52 54 58 60 61 66 67 68 69 70 71 72 73 75 77 81 84 86 88 90 92 93 95 96 97 98 99 100 105 106 107 114 117 119 121 122 123 125 126 130 131 135 136 146 147 148 149 152 153 154 156 158 160 161 163 168 170 171 174 179 180 182 184 186 189 ...
result:
ok 176756 numbers