QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#688628 | #862. Social Justice | 5toubun_no_hanayome | TL | 0ms | 0kb | C++14 | 3.3kb | 2024-10-30 11:49:00 | 2024-10-30 11:49:00 |
answer
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a);i <= (b);++i)
#define per(i, a, b) for(int i = (a);i >= (b);--i)
#define lc (k << 1)
#define rc (k << 1 | 1)
#define lowbit(x) ((x) & -(x))
#define odd(x) ((x) & 1)
#define even(x) (!odd(x))
#define fir first
#define sec second
#define pb push_back
#define il inline
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define i128 __int128
#define f128 __float128
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define SZ(x) ((int)(x).size())
#define debug(x) cerr << "In Line " << __LINE__ << " the " << #x << " = " << (x) << "\n"
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<class T> using vc = vector<T>;
template<class Tx, class Ty>
il void chkmx(Tx& x, const Ty y) {x = max<common_type_t<Tx, Ty>>(x, y);}
template<class Tx, class Ty>
il void chkmn(Tx& x, const Ty y) {x = min<common_type_t<Tx, Ty>>(x, y);}
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3fll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
bool ms;
char buf[1 << 20], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
template<class T>
il void read(T& x) {
char ch;int f = 1;x = 0;
do {ch = getchar();if(ch == '-')f = -1;} while(!isdigit(ch));
do {x = x * 10 + (ch ^ 48);ch = getchar();} while(isdigit(ch));
x *= f;
}
template<class T, class... Arg>
il void read(T& x, Arg&... nums) {
read(x), read(nums...);
}
const int N = 2e5 + 5;
int a[N], id[N];
int c[N];
ll pre[N];
void solve() {
int n, p, q;
read(n);
rep(i, 1, n)
read(a[i]);
read(p, q);
iota(id + 1, id + n + 1, 1);
sort(id + 1, id + n + 1, [&](const int& x, const int& y) {
return a[x] < a[y];
});
rep(i, 1, n)
pre[i] = pre[i - 1] + a[id[i]];
int x = n;
rep(i, 1, n) {
int l = 1, r = i, ans = i;
while(l <= r) {
int mid = l + r >> 1;
if((pre[i] - pre[mid - 1]) * p >= 1ll * a[id[i]] * (i - mid + 1) * q) {
ans = mid;
r = mid - 1;
} else
l = mid + 1;
}
chkmn(x, n - (i - ans + 1));
}
x = n - x;
rep(i, x, n) {
ll sum = pre[i] - pre[i - x];
if(sum * p < 1ll * a[id[i]] * x * q)
continue;
sum -= a[id[i - x + 1]];
int l = 1, r = i - x + 1, ans = i - x + 1;
while(l <= r) {
int mid = l + r >> 1;
if((sum + a[id[mid]]) * p >= 1ll * a[id[i]] * x * q) {
ans = mid;
r = mid - 1;
} else
l = mid + 1;
}
++c[ans], --c[i + 1];
}
vc<int> ans;
rep(i, 1, n) {
c[i] += c[i - 1];
if(!c[i])
ans.pb(id[i]);
}
sort(all(ans));
cout << SZ(ans) << "\n";
rep(i, 0, SZ(ans) - 1)
cout << ans[i] << " \n"[i == SZ(ans) - 1];
}
bool mt;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cerr << fabs(&ms - &mt) / 1024 / 1024 << "\n";
int t;
cin >> t;
while(t--)
solve();
cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}
詳細信息
Test #1:
score: 0
Time Limit Exceeded
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