QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#876333#8621. KnapsacksuperguymjRE 0ms0kbC++202.2kb2025-01-30 20:00:092025-01-30 20:00:09

Judging History

This is the latest submission verdict.

  • [2025-01-30 20:00:09]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 0kb
  • [2025-01-30 20:00:09]
  • Submitted

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;
}

详细

Test #1:

score: 0
Runtime Error

input:

6
4 3 8 1 5 4

output:


result: