QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#876323 | #8621. Knapsack | superguymj# | RE | 0ms | 0kb | C++20 | 2.1kb | 2025-01-30 19:57:25 | 2025-01-30 19:57:33 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,x,y) for (int i = x; i <= y; i++)
#define repd(i,x,y) for (int i = x; i >= y; i--)
using namespace std;
using i64 = long long;
int main() {
int n;
cin >> n;
vector<i64> a(n);
rep(i,0,n-1) {
cin >> a[i];
}
auto work = [&](vector<i64> a, char c) -> string {
string res(a.size(), '.');
vector<pair<i64, int>> pr;
int p = 0;
for (auto i : a) {
pr.emplace_back(i, p++);
}
sort(pr.begin(), pr.end());
for (int i = 0; i < a.size(); i++) {
a[i] = pr[i].first;
}
constexpr i64 T = 1E11;
constexpr int K = 20;
vector<pair<i64, int>> A;
rep(i,1,(1<<K)-1) {
i64 tmp = 0;
rep(j,0,K-1) {
if (i >> j & 1) {
tmp += a[j];
}
}
A.emplace_back(tmp, i);
// cerr << tmp << '\n';
}
sort(A.begin(), A.end());
rep(i,1,(1<<K)-1) {
i64 tmp = 0;
rep(j,0,K-1) {
if (i >> j & 1) {
tmp += a[j + K];
}
}
if (tmp >= T) {
continue;
}
auto it = lower_bound(A.begin(), A.end(), make_pair(T - tmp, 0));
if (it < A.end() && it->first == T - tmp) {
cerr << tmp << '\n';
rep(j,0,K-1) {
if ((it->second) >> j & 1) {
res[pr[j].second] = c;
}
if (i >> j & 1) {
res[pr[j + K].second] = c;
}
}
return res;
}
}
assert(0);
return res;
};
constexpr int L = 3333;
cout << work(vector(a.begin(), a.begin() + L), 'A')
+ work(vector(a.begin() + L, a.begin() + 2 * L), 'B')
+ work(vector(a.begin() + 2 * L, a.end()), 'C') << '\n';
return 0;
}
詳細信息
Test #1:
score: 0
Runtime Error
input:
6 4 3 8 1 5 4