QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#51085#1282. Necklaceckiseki#WA 81ms3680kbC++5.1kb2022-09-30 18:01:332022-09-30 18:01:36

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-30 18:01:36]
  • 评测
  • 测评结果:WA
  • 用时:81ms
  • 内存:3680kb
  • [2022-09-30 18:01:33]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using lld = int64_t;
static constexpr lld INF = lld(1) << 60;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<pair<int,int>> a(n);
        for (auto &[ai, _] : a) cin >> ai;
        for (auto &[_, ai] : a) cin >> ai;
        vector<vector<pair<lld, int>>> v(n);
        for (int i = 0; i < n; ++i) {
            v[a[i].first - 1].emplace_back(a[i].second, i);
        }
        for (auto &vi : v) sort(vi.begin(), vi.end(), greater<>());

        vector<pair<int64_t,int>> nsm;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < int(v[i].size()); ++j) {
                if (v[i][j].first >= 0) continue;
                nsm.emplace_back(v[i][j].first, i);
            }
        }
        sort(nsm.begin(), nsm.end(), greater<>());
        vector<vector<int>> np(n);
        for (int i = 0; i < int(nsm.size()); ++i) {
            np[nsm[i].second].push_back(i);
            if (i > 0) {
                nsm[i].first += nsm[i - 1].first;
            }
        }
        auto get_k = [&nsm, &np](int i, int k) {
            if (nsm.size() - np[i].size() < k) return -INF;
            size_t l = 0, r = nsm.size();
            while (r - l > 1) {
                size_t m = (l + r) >> 1;
                auto it = upper_bound(np[i].begin(), np[i].end(), m);
                size_t d = m - (it - np[i].begin());
                if (d <= k) l = m;
                else r = m;
            }
            return nsm[l].first;
        };

        vector<pair<lld,int>> psm(n + 1);
        for (auto &vi : v) {
            lld csm = 0;
            int l = 0;
            int j;
            for (j = 0; j < int(vi.size()); ++j) {
                if (vi[j].first < 0) {
                    break;
                }
                ++l;
                csm += vi[j].first;
                psm[j + 1].first += csm;
                psm[j + 1].second += l;
            }
            while (j < n) {
                psm[j + 1].first += csm;
                psm[j + 1].second += l;
                ++j;
            }
        }

        tuple<lld, int, int> ans = {-INF, -1, -1};

        for (int i = 0; i < n; ++i) {
            lld ns = 0;
            int nc = 0;
            for (int j = 0; j < int(v[i].size()); ++j) {
                auto cv = v[i][j].first;
                if (cv < 0) {
                    ns += cv;
                    nc++;
                }
                lld cs = psm[j + 1].first + ns;
                int cl = psm[j + 1].second + nc;
                if ((j + 1) > cl / 2) {
                    int k = (j + 1) * 2 - cl;
                    auto vk = get_k(i, k);
                    if (vk == -INF) continue;
                    cs += vk;
                }
                
                tuple<lld, int, int> cans = {cs, i, j + 1};
                ans = max(ans, cans);
            }
        }

        if (auto [s, c, l] = ans; s == -INF) {
            cout << -1 << '\n';
        } else {
            vector<int> p(n);
            for (int i = 0; i < n; ++i) {
                p[i] = l;
                if (i != c) {
                    p[i] = min<int>(l, v[i].size());
                    for (int j = 0; j < l; ++j) {
                        if (j == v[i].size()) break;
                        if (v[i][j].first < 0) {
                            p[i] = j;
                            break;
                        }
                    }
                }
            }
            int totl = accumulate(p.begin(), p.end(), 0);
            if (l > totl / 2) {
                priority_queue<pair<int64_t,int>> pq;
                for (int i = 0; i < n; ++i) {
                    if (i == c) continue;
                    if (p[i] < v[i].size()) {
                        pq.emplace(v[i][p[i]++].first, i);
                    }
                }
                while (l > totl / 2) {
                    totl++;
                    auto [_, i] = pq.top(); pq.pop();
                    if (p[i] < v[i].size()) {
                        pq.emplace(v[i][p[i]++].first, i);
                    }
                }
            }

            vector<int> seq;
            priority_queue<pair<int,int>> pq;
            for (int i = 0; i < n; ++i) {
                if (p[i] > 0) pq.emplace(p[i], i);
            }
            while (not pq.empty()) {
                auto [_, i] = pq.top(); pq.pop();
                p[i]--;
                seq.push_back(v[i][p[i]].second);
                if (pq.empty()) {
                    assert(p[i] == 0);
                    break;
                }
                auto [__, j] = pq.top(); pq.pop();
                p[j]--;
                seq.push_back(v[j][p[j]].second);

                if (p[i] > 0) {
                    pq.emplace(p[i], i);
                }
                if (p[j] > 0) {
                    pq.emplace(p[j], j);
                }

            }
            cout << seq.size() << '\n';
            for (size_t i = 0; i < seq.size(); ++i)
                cout << seq[i] + 1 << " \n"[i + 1 == seq.size()];
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3516kb

input:

4
4
1 1 1 1
1 2 3 4
4
1 1 2 2
1 2 3 4
8
2 6 5 4 3 1 7 7
-1 4 -1 2 10 -1 3 0
6
5 5 3 3 4 6
5 8 0 -1 -2 -7

output:

-1
4
3 1 4 2
5
8 2 7 4 5
4
1 4 2 3

result:

ok 4 cases.

Test #2:

score: -100
Wrong Answer
time: 81ms
memory: 3680kb

input:

36398
6
4 6 4 4 5 2
7 -9 -9 4 -1 -8
2
1 1
-8 -5
2
2 1
10 7
9
5 6 5 8 2 3 3 7 8
-7 5 -5 7 8 7 -5 -5 8
2
1 2
6 -8
9
2 3 3 5 3 9 3 9 3
5 2 -2 5 -8 -5 -3 6 -2
4
4 2 4 1
-1 -1 10 -4
4
3 1 2 1
-9 -6 4 10
5
4 3 4 1 4
-8 1 6 10 -8
6
2 6 3 5 4 1
1 -7 4 0 6 -6
6
6 6 5 2 1 2
3 1 2 -8 -7 0
10
2 9 10 7 8 7 6 7 6...

output:

2
5 1
-1
2
1 2
5
4 2 9 6 5
2
2 1
4
8 4 2 1
2
3 2
2
3 4
3
3 2 4
4
4 5 3 1
4
2 3 1 6
5
4 9 6 7 10
4
2 9 6 3
6
8 6 2 7 4 3
5
2 6 3 1 9
-1
6
5 2 3 1 8 6
3
1 3 4
2
2 4
-1
4
5 1 2 3
2
2 1
4
7 2 8 3
7
4 2 7 5 6 1 3
2
2 1
5
8 6 4 2 7
2
6 5
-1
5
8 7 4 1 3
4
8 2 6 5
-1
2
3 1
5
6 1 4 3 2
2
2 1
-1
3
5 9 3
2
1 2...

result:

wrong answer case #1: expected -1 or [3, 6]