QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#54280#862. Social Justiceckiseki#WA 5ms3724kbC++2.4kb2022-10-07 19:02:532022-10-07 19:02:54

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-07 19:02:54]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:3724kb
  • [2022-10-07 19:02:53]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

int64_t cdiv(int64_t a, int64_t b) {
    return (a + b - 1) / b;
}

signed main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int64_t> a(n);
        vector<int64_t> pre(n + 1);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        vector<int> id(n);
        iota(id.begin(), id.end(), 0);
        sort(id.begin(), id.end(), [&](int i, int j) { return a[i] < a[j]; });

        int p, q;
        cin >> p >> q; // K = p / q
        sort(a.begin(), a.end());
        for (int i = 0; i < n; i++)
            pre[i + 1] = pre[i] + a[i];

        const auto ok = [&](int l, int r) {
            // using llf = long double;
            const int ret = a[r - 1] * q * (r - l) <= p * (pre[r] - pre[l]);
            // cerr << a[r-1] << "<=" << (pre[r]-pre[l])/llf(r-l)*p/q << ' ' << ret << endl;
            return ret;
        };

        vector<int> left(n);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int l = i;
            for (int s = 1<<20; s; s >>= 1) {
                if (l - s >= 0 && ok(l - s, i + 1)) {
                    l -= s;
                }
            }
            left[i] = l;
            ans = max(ans, i + 1 - l);
        }

        vector<int> sum(n + 1);
        for (int i = 0; i < n; i++) {
            if (i + 1 - left[i] != ans) continue;
            // a[i] <= (sum - a[left[i]] + a[x]) / ans * K
            // a[x] >= ceil(a[i] * ans / K) - (sum - a[left[i]])
            // x < left[i];
            int64_t U = cdiv(a[i] * ans * q, p) - (pre[i + 1] - pre[left[i] + 1]);
            int j = lower_bound(a.begin(), a.begin() + left[i], U) - a.begin();
            int k = upper_bound(a.begin(), a.end(), a[i]) - a.begin();
            sum[j] += 1;
            sum[k] -= 1;
        }

        for (int i = 1; i < n; i++)
            sum[i] += sum[i - 1];

        vector<int> res;
        for (int i = 0; i < n; i++)
            if (sum[i] == 0)
                res.push_back(id[i]+1);
        cout << res.size() << '\n';
        for (size_t i = 0; i < res.size(); i++) {
            cout << res[i];
            if (i + 1 != res.size())
                cout << ' ';
        }
        cout << '\n';

        // cerr << "max = " << ans << endl;
        // for (int i = 0; i < n; i++) {
        //     cerr << left[i] << ',';
        // }
        // cerr << endl;

    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3624kb

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: 5ms
memory: 3724kb

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
5 1
3
4 2 6
6
14 4 12 2 6 16
8
14 4 24 12 22 2 16 6
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 20 19 18
0

2
2 8
2
12 9
2
2 14
10
4 5 6 7 18 1 15 13 14 20
2
16 9
2
18 16
2
13 5
10
11 20 19 18 15 9 6 5 4 16
2
19 5
2
13 5
2
10 15
2
14 17
10
11 20 18...

result:

wrong answer 16th numbers differ - expected: '1', found: '5'