QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#51108 | #1282. Necklace | ckiseki# | WA | 87ms | 3552kb | C++ | 5.7kb | 2022-09-30 20:30:01 | 2022-09-30 20:30:02 |
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);
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