QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#51090#1282. Necklaceckiseki#WA 80ms3740kbC++5.3kb2022-09-30 18:34:402022-09-30 18:34:43

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:34:43]
  • 评测
  • 测评结果:WA
  • 用时:80ms
  • 内存:3740kb
  • [2022-09-30 18:34:40]
  • 提交

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);
        vector<vector<int64_t>> nps(n);
        for (int i = 0; i < int(nsm.size()); ++i) {
            np[nsm[i].second].push_back(i);
            nps[nsm[i].second].push_back(nsm[i].first);
            if (i > 0) {
                nsm[i].first += nsm[i - 1].first;
            }
        }
        for (int i = 0; i < n; ++i) {
            for (size_t j = 1; j < nps[i].size(); ++j) {
                nps[i][j] += nps[i][j - 1];
            }
        }
        auto get_k = [&nsm, &np, &nps](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;
            }
            auto it = upper_bound(np[i].begin(), np[i].end(), l);
            auto ret = nsm[l].first;
            if (it != np[i].begin()) {
                ret -= nps[i][prev(it) - np[i].begin()];
            }
            return ret;
        };

        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<vector<int>> o(l); 
            size_t cp = 0;
            for (int i = 0; i < n; ++i) {
                if (i == c) continue;
                for (int j = 0; j < p[i]; ++j) {
                    o[cp].push_back(v[i][j].second);
                    if (++cp == l) cp = 0;
                }
            }
            vector<int> seq;
            for (size_t i = 0; i < l; ++i) {
                seq.push_back(v[c][i].second);
                for (auto x : o[i]) seq.push_back(x);
            }
            cout << seq.size() << '\n';
            for (size_t i = 0; i < seq.size(); ++i)
                cout << seq[i] + 1 << " \n"[i + 1 == seq.size()];
        }
    }
    return 0;
}

詳細信息

Test #1:

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

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
4 2 3 1
5
7 5 2 8 4
4
3 2 4 1

result:

ok 4 cases.

Test #2:

score: -100
Wrong Answer
time: 80ms
memory: 3740kb

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
9 5 2 4 6
2
2 1
4
8 1 2 4
2
2 3
2
3 4
3
3 4 2
4
4 1 3 5
4
1 6 2 3
5
6 10 9 4 7
4
2 3 6 9
6
3 4 2 7 8 6
5
2 9 1 3 6
-1
6
5 6 8 1 3 2
3
1 4 3
2
2 4
-1
4
3 2 5 1
2
2 1
4
7 3 8 2
7
6 3 1 7 4 2 5
2
2 1
5
2 7 6 8 4
2
6 5
-1
5
3 1 7 8 4
4
5 6 8 2
-1
2
1 3
5
1 2 3 4 6
2
2 1
-1
3
5 3 9
2
1 2...

result:

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