QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#876333 | #8621. Knapsack | superguymj | RE | 0ms | 0kb | C++20 | 2.2kb | 2025-01-30 20:00:09 | 2025-01-30 20:00:09 |
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];
}
const i64 l = *min_element(a.begin(), a.end());
const i64 r = *max_element(a.begin(), a.end());
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;
}
const i64 T = 20 * 20 * (r - l) + 20 * 20 * l;
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
6 4 3 8 1 5 4