QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#51108#1282. Necklaceckiseki#WA 87ms3552kbC++5.7kb2022-09-30 20:30:012022-09-30 20:30:02

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 20:30:02]
  • 评测
  • 测评结果:WA
  • 用时:87ms
  • 内存:3552kb
  • [2022-09-30 20:30:01]
  • 提交

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];
            }
        }
        
        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) {

            int cp = 0;
            auto get_k = [&nsm, &np, &nps, i, &cp](int k) {
                if (nsm.size() - np[i].size() < k) return -INF;
                int needp = k + cp;
                while (cp < int(np[i].size()) and needp >= np[i][cp]) {
                    cp++;
                    needp = k + cp;
                }
                auto r = nsm[needp].first;
                if (cp > 0) r -= nps[i][cp - 1];
                return r;
            };


            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 == 0 and cl <= 2) continue;
                if (cs <= get<0>(ans)) continue;
                if ((j + 1) > cl / 2) {
                    int k = (j + 1) * 2 - cl;
                    auto vk = get_k(k);
                    if (vk == -INF) continue;
                    cs += vk;
                }
                
                tuple<lld, int, int> cans = {cs, i, j + 1};
                ans = max(ans, cans);
            }
        }

        auto [s, c, l] = ans;

        vector<pair<int64_t, int>> meow;
        for (int i = 0; i < n; ++i) {
            if (v[i].empty()) continue;
            meow.emplace_back(v[i][0].first, i);
        }
        sort(meow.begin(), meow.end(), greater<>());
        if (meow.size() >= 3 and meow[0].first + meow[1].first + meow[2].first > s) {
            cout << 3 << '\n';
            cout << v[meow[0].second][0].second + 1 << ' ' << v[meow[1].second][0].second + 1 << ' ' << v[meow[2].second][0].second + 1 << '\n';
            continue;
        }

        if (s == -INF) {
            cout << -1 << '\n';
        } else {
            vector<int> p(n);
            for (int i = 0; i < n; ++i) {
                p[i] = min<int>(l, v[i].size());
                if (i != c) {
                    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();
                    p[i]++;
                    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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

result:

ok 4 cases.

Test #2:

score: -100
Wrong Answer
time: 87ms
memory: 3524kb

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:

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

result:

wrong answer case #1: jury has better solution 2 vs -16