QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#51085 | #1282. Necklace | ckiseki# | WA | 81ms | 3680kb | C++ | 5.1kb | 2022-09-30 18:01:33 | 2022-09-30 18:01:36 |
Judging History
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;
}
详细
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]