QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#688628#862. Social Justice5toubun_no_hanayomeTL 0ms0kbC++143.3kb2024-10-30 11:49:002024-10-30 11:49:00

Judging History

你现在查看的是最新测评结果

  • [2024-10-30 11:49:00]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [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

output:


result: