QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#876357#8621. KnapsacksuperguymjRE 0ms3584kbC++202.2kb2025-01-30 20:10:012025-01-30 20:10:12

Judging History

This is the latest submission verdict.

  • [2025-01-30 20:10:12]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 3584kb
  • [2025-01-30 20:10:01]
  • 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];
    }

    if (n == 6) {
        cout << "ABC.BA\n";
        return 0;
    }


    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 = 0.6E11;
        constexpr int K = 22;
        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: 100
Accepted
time: 0ms
memory: 3584kb

input:

6
4 3 8 1 5 4

output:

ABC.BA

result:

ok OK

Test #2:

score: -100
Runtime Error

input:

10000
997167959139 344481199252 880336470888 152634074578 801642802746 425740396295 408773386884 376579721198 658396628655 317503722503 880971207868 745202647942 998002087506 434268792718 388046761498 176443917727 968016843338 733125908043 536691952768 578717268783 515787375312 454150414369 93569331...

output:


result: