QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#570877#8790. First BillionHTensorTL 801ms260804kbC++174.8kb2024-09-17 18:38:132024-09-17 18:38:14

Judging History

你现在查看的是最新测评结果

  • [2024-09-17 18:38:14]
  • 评测
  • 测评结果:TL
  • 用时:801ms
  • 内存:260804kb
  • [2024-09-17 18:38:13]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 结构体用于存储子集和及其对应的元素索引
struct Subset {
    ll sum;
    vector<int> indices;
};

// 全局变量
const int B = 36; // 桶的数量
const ll TARGET = 1000000000LL;

// 分桶函数
vector<vector<pair<ll, int>>> distributeBuckets(int N, const vector<ll> &a) {
    // 贪心分配:将较大的数先分配到桶中,使得每个桶的总和尽可能均衡
    vector<vector<pair<ll, int>>> buckets(B, vector<pair<ll, int>>());
    
    // 创建一个数组记录每个桶的当前总和
    vector<ll> bucketSums(B, 0);
    
    // 将元素按降序排序
    vector<pair<ll, int>> sortedA(N);
    for(int i=0; i<N; ++i){
        sortedA[i] = {a[i], i+1}; // 1-based indexing
    }
    sort(sortedA.begin(), sortedA.end(), [&](const pair<ll, int> &a, const pair<ll, int> &b) -> bool{
        if(a.first != b.first) return a.first > b.first;
        return a.second < b.second;
    });
    
    // 贪心分配
    for(auto &[value, idx] : sortedA){
        // 找到当前总和最小的桶
        int minBucket = min_element(bucketSums.begin(), bucketSums.end()) - bucketSums.begin();
        buckets[minBucket].emplace_back(value, idx);
        bucketSums[minBucket] += value;
    }
    
    return buckets;
}

// 生成所有子集和
vector<Subset> generateSubsets(const vector<pair<ll, int>> &bucket) {
    int n = bucket.size();
    vector<Subset> subsets;
    subsets.emplace_back(Subset{0, {}}); // 空集
    
    for(int i=0; i<n; ++i){
        int currentSize = subsets.size();
        for(int j=0; j<currentSize; ++j){
            Subset newSubset = subsets[j];
            newSubset.sum += bucket[i].first;
            newSubset.indices.push_back(bucket[i].second);
            subsets.push_back(newSubset);
        }
    }
    return subsets;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N;
    cin >> N;
    vector<ll> a(N);
    for(auto &x: a) cin >> x;
    
    // 分配到36个桶中
    vector<vector<pair<ll, int>>> buckets = distributeBuckets(N, a);
    
    // 分成两部分,前18个桶和后18个桶
    int halfB = B / 2;
    vector<vector<pair<ll, int>>> firstHalf(buckets.begin(), buckets.begin() + halfB);
    vector<vector<pair<ll, int>>> secondHalf(buckets.begin() + halfB, buckets.end());
    
    // 生成前半部分所有可能的子集和
    vector<Subset> subsetsFirst;
    subsetsFirst.emplace_back(Subset{0, {}}); // 空集
    for(auto &bucket : firstHalf){
        vector<Subset> temp = generateSubsets(bucket);
        vector<Subset> newSubsets;
        for(auto &s1 : subsetsFirst){
            for(auto &s2 : temp){
                Subset combined;
                combined.sum = s1.sum + s2.sum;
                combined.indices = s1.indices;
                combined.indices.insert(combined.indices.end(), s2.indices.begin(), s2.indices.end());
                newSubsets.push_back(combined);
            }
        }
        subsetsFirst = move(newSubsets);
    }
    
    // 生成后半部分所有可能的子集和
    vector<Subset> subsetsSecond;
    subsetsSecond.emplace_back(Subset{0, {}}); // 空集
    for(auto &bucket : secondHalf){
        vector<Subset> temp = generateSubsets(bucket);
        vector<Subset> newSubsets;
        for(auto &s1 : subsetsSecond){
            for(auto &s2 : temp){
                Subset combined;
                combined.sum = s1.sum + s2.sum;
                combined.indices = s1.indices;
                combined.indices.insert(combined.indices.end(), s2.indices.begin(), s2.indices.end());
                newSubsets.push_back(combined);
            }
        }
        subsetsSecond = move(newSubsets);
    }
    
    // 将后半部分的子集和存入哈希表
    unordered_map<ll, vector<vector<int>>> hashSecond;
    for(auto &s : subsetsSecond){
        hashSecond[s.sum].emplace_back(s.indices);
    }
    
    // 遍历前半部分,寻找匹配
    bool found = false;
    vector<int> result;
    for(auto &s : subsetsFirst){
        ll complement = TARGET - s.sum;
        if(hashSecond.find(complement) != hashSecond.end()){
            // 找到一个匹配
            // 取第一个匹配的子集
            result = s.indices;
            // 添加后半部分的索引
            for(auto idx : hashSecond[complement][0]){
                result.push_back(idx);
            }
            found = true;
            break;
        }
    }
    
    if(found){
        // 输出结果
        cout << result.size();
        for(auto idx: result) cout << " " << idx;
        cout << "\n";
    }
    else{
        // 根据题意,一定有解
        cout << "No solution found.\n";
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3788kb

input:

10
386413329 88494216 245947398 316438989 192751270 204627269 65749456 3938400 150458676 345180997

output:

5 10 4 3 2 8

result:

ok OK (n = 10)

Test #2:

score: 0
Accepted
time: 1ms
memory: 3968kb

input:

10
119486233 299942886 169540407 349937991 597883752 32230162 140514533 57341098 12602102 220520836

output:

5 4 10 3 7 1

result:

ok OK (n = 10)

Test #3:

score: 0
Accepted
time: 7ms
memory: 5824kb

input:

14
384615281 84612238 83310504 54746763 142296081 56775470 128760350 343006424 177232390 214368720 67220468 21895072 16352717 224807522

output:

7 8 14 5 2 3 11 4

result:

ok OK (n = 14)

Test #4:

score: 0
Accepted
time: 7ms
memory: 5664kb

input:

14
270208635 14270307 89661499 113578022 47687195 101043954 38775146 208193324 650676076 351701957 3427619 59535626 24230888 27009752

output:

7 10 1 4 6 3 12 2

result:

ok OK (n = 14)

Test #5:

score: 0
Accepted
time: 33ms
memory: 34348kb

input:

20
61638928 106712373 5946815 178135484 4937573 111395400 15504655 67139983 101814514 312223647 130341028 43244171 37671364 54108486 337181317 37924824 153793862 70383750 102917244 66984582

output:

10 10 4 11 9 18 8 14 12 13 5

result:

ok OK (n = 20)

Test #6:

score: 0
Accepted
time: 24ms
memory: 34456kb

input:

20
67858098 61231428 99398662 1883806 82465954 303619377 87516412 154956240 94872199 76508350 13276828 136541811 203282099 99160366 127539385 13364660 141176136 39751629 67888657 127707903

output:

10 13 8 17 12 3 14 5 1 11 4

result:

ok OK (n = 20)

Test #7:

score: 0
Accepted
time: 43ms
memory: 34632kb

input:

24
17125795 281143405 10375259 196293002 158174864 34520650 52919232 87393970 99085271 62281508 67168428 55174991 54533464 51393059 89276370 41441658 72793517 30466999 73758332 97064918 111541434 142047546 12934221 101092107

output:

12 4 5 22 20 15 19 17 10 13 18 23 3

result:

ok OK (n = 24)

Test #8:

score: 0
Accepted
time: 39ms
memory: 34448kb

input:

24
70224368 148769600 36654748 23404220 15009825 57449487 46896672 6065662 10377031 133719710 23220853 184445684 8462667 88501546 155244839 229323557 140109402 52520271 78995771 75721556 87987586 118427778 107013825 101453342

output:

12 12 17 10 23 21 19 20 1 7 3 11 5

result:

ok OK (n = 24)

Test #9:

score: 0
Accepted
time: 35ms
memory: 34352kb

input:

28
122321206 60841271 22767116 183943582 6247754 32767541 19129802 21313874 144503909 59360441 12259051 19044256 50267333 25766572 133411289 32253746 102412217 46186594 55413161 39907615 52325783 86862071 185310732 138228874 22000146 149813853 98156445 77183766

output:

14 4 26 15 1 17 28 2 18 6 16 8 12 11 5

result:

ok OK (n = 28)

Test #10:

score: 0
Accepted
time: 40ms
memory: 34536kb

input:

28
213829745 40823140 14876795 22548901 35958464 159026037 106482651 52655603 76733934 102794554 100713772 80174862 125840182 3619651 74158077 27699586 14743901 68385227 55117143 39623241 67325444 95072408 46052588 46086093 11650160 66077724 149558313 102371804

output:

14 6 27 13 10 11 22 21 19 20 5 16 3 17 25

result:

ok OK (n = 28)

Test #11:

score: 0
Accepted
time: 28ms
memory: 34464kb

input:

30
38319400 42378812 172927254 71697590 118171420 5615707 8117586 107362865 18142211 89646810 51847201 37450061 138487251 116358215 15432103 13621837 15084921 15012145 42848714 71166566 37074067 11354748 10702902 244865332 41244161 102695984 217681174 21564320 89607508 33521135

output:

17 27 13 10 29 4 20 11 19 2 25 1 30 28 15 17 22 7

result:

ok OK (n = 30)

Test #12:

score: 0
Accepted
time: 33ms
memory: 34468kb

input:

30
239221492 41835739 80260950 47743386 50052259 31410042 1676838 63813733 47622772 150506632 188312503 190432229 6783832 111319580 122183547 37258127 12116231 29322396 58095114 47089744 9262724 204673438 11840273 64585542 11797425 4134848 56164171 30717831 46921664 2844938

output:

15 12 11 15 14 8 27 5 4 20 16 28 18 17 25 7

result:

ok OK (n = 30)

Test #13:

score: 0
Accepted
time: 38ms
memory: 34292kb

input:

30
52710609 39033241 15723499 29898108 62692739 138885388 137151511 90118964 15492963 61261380 35071118 195401367 64471367 39372151 70235925 114596786 27917908 29285928 11044525 11941155 12716377 1533910 24799365 265236184 104128755 17709404 4856890 204911218 17131655 104669610

output:

15 28 12 7 16 15 10 1 14 2 17 3 9 21 20 22

result:

ok OK (n = 30)

Test #14:

score: 0
Accepted
time: 33ms
memory: 34364kb

input:

30
71176974 17279544 55258168 53966156 72625891 26990484 32947301 24238341 23523054 74032236 11115471 37748780 197790571 37391026 97632202 141185045 78244645 55562875 112526424 172476633 23788890 38112613 43056490 59434820 126859036 3192138 33541518 45692823 37948025 194661826

output:

16 20 16 25 19 17 3 28 23 22 29 12 7 6 8 9 26

result:

ok OK (n = 30)

Test #15:

score: 0
Accepted
time: 32ms
memory: 34452kb

input:

30
14207343 153611578 16683105 27989436 25086738 33243492 111638179 47972430 19637539 35808627 12134813 60480737 68270077 122259678 37288938 86244354 36408417 58808264 33320672 9412909 176141849 93548029 55980295 128091293 13973554 27108753 77442637 246155003 18397254 152654007

output:

17 30 24 14 7 16 13 12 18 8 10 4 26 29 3 1 25 20

result:

ok OK (n = 30)

Test #16:

score: 0
Accepted
time: 66ms
memory: 37812kb

input:

34
56158267 5346691 37606439 26760105 123601340 44674017 43239382 23064728 175228414 72881379 25027579 73516264 13748174 69400907 47140260 105416679 45175827 129325284 14737537 147069844 84833847 91264478 15805185 5872801 60910166 8127595 87459162 153141045 24930343 27343635 11563194 56545951 773088...

output:

17 18 5 16 21 33 12 10 25 15 17 7 3 30 4 8 13 26

result:

ok OK (n = 34)

Test #17:

score: 0
Accepted
time: 75ms
memory: 37932kb

input:

34
6553507 21827844 163114470 285889880 111444346 91096849 9875033 155790401 48814749 32707381 4390111 3512692 227551194 24852373 35077911 52304487 14043961 21718427 153749785 10890230 81276988 24039619 19484842 19224458 60528342 80892446 43482284 3024810 18734584 44556796 18825186 16762113 91529698...

output:

18 8 19 5 33 21 25 16 9 30 27 15 10 18 23 24 17 7 11

result:

ok OK (n = 34)

Test #18:

score: 0
Accepted
time: 61ms
memory: 37788kb

input:

34
6510953 149563269 90208590 17087264 54154081 48557639 30119336 148147082 30167332 41026594 23352774 7503341 127871531 56098411 30309985 90903962 20775544 12444200 23139566 173775423 39698044 23256886 32599474 19795212 62981178 43614848 71114165 138887136 8874281 1542445 96191893 14339496 11492279...

output:

16 28 13 33 31 16 3 25 14 6 21 23 9 11 17 32 18

result:

ok OK (n = 34)

Test #19:

score: 0
Accepted
time: 59ms
memory: 37932kb

input:

34
76165834 52107905 64590881 31631692 6704569 151480738 146750957 43792305 11263200 3762351 55603212 9648993 8323006 63561211 39768967 5565808 18484315 47155971 95389177 39661235 158388679 115049517 90536356 16230 36970573 69805600 69394080 162875090 33332306 141161983 59599679 47506416 36779765 71...

output:

19 6 22 23 1 26 3 14 31 11 2 18 15 20 25 17 34 5 16 24

result:

ok OK (n = 34)

Test #20:

score: 0
Accepted
time: 63ms
memory: 37808kb

input:

34
54830390 113752786 1256295 65643133 17997234 93531549 17982160 52907635 60890541 46120250 33991135 36315875 125481200 21717043 2931945 204316378 34997684 89844853 71646618 44706963 444743 16090084 221143946 50917758 48030413 93143102 2161608 69130708 43539172 92362195 26368947 33556321 68574624 4...

output:

20 2 6 30 18 19 33 4 9 1 24 10 34 12 11 32 14 5 15 3 21

result:

ok OK (n = 34)

Test #21:

score: 0
Accepted
time: 774ms
memory: 260620kb

input:

38
61295704 120959759 13190535 82400573 19952027 65933932 6386901 31702075 26739290 8114929 40114285 36513729 14021915 36412926 103842230 23073744 64285890 7726874 7069826 11026974 112061519 86593033 24948152 31660315 58256958 56241422 21694304 2454321 4008850 145718408 71162340 18472714 32541051 17...

output:

24 21 22 37 36 4 31 17 1 25 26 11 12 8 9 27 5 3 20 10 18 19 28 7 29

result:

ok OK (n = 38)

Test #22:

score: 0
Accepted
time: 801ms
memory: 260680kb

input:

38
6041181 60606547 25009256 67510442 13154279 42254607 13913303 70468898 83661964 9693776 14673029 65391499 20900136 70775729 232451283 120308939 8000114 57176181 37323456 8856486 83542977 169853088 65998342 73938927 89977321 33127725 18524012 98889224 37672769 64174135 84811684 35339006 11678853 4...

output:

25 21 24 14 8 4 12 30 2 18 36 6 29 19 32 26 3 35 13 27 7 5 33 20 37 1

result:

ok OK (n = 38)

Test #23:

score: 0
Accepted
time: 783ms
memory: 260556kb

input:

38
18362326 19090432 36949939 201073371 81787520 9144779 12700980 106084822 215335010 131147703 22973034 43876431 9268739 137958148 6855146 15674059 42021492 40619493 3662247 36558198 231081433 21696469 10761956 35417110 18250457 42223480 7356242 104352860 4479650 98688233 20581514 59307013 47254982...

output:

21 10 8 28 30 5 32 33 12 26 18 3 20 24 34 37 11 25 16 23 6 29

result:

ok OK (n = 38)

Test #24:

score: 0
Accepted
time: 755ms
memory: 260804kb

input:

38
104562951 26015894 3145542 123734324 14548111 105001982 102528865 56074111 16743701 102313381 78956994 13474659 65680616 24114824 12197913 111320556 7216879 11175792 7992693 1413099 101341761 27655187 3017819 4970522 3562488 106653156 111044688 1609530 32741939 35813979 25952252 72341688 22966055...

output:

23 6 1 7 10 21 32 13 8 30 36 34 29 22 2 31 14 15 18 19 38 17 20 28

result:

ok OK (n = 38)

Test #25:

score: 0
Accepted
time: 732ms
memory: 260788kb

input:

38
170912121 22871446 35334264 15023151 4773792 1434560 32319430 37415290 39242013 16597189 6001330 55658237 36180315 18572198 19827812 35336501 31560303 54548994 74446747 46057860 173191453 54272395 24146280 193702375 56678360 36796796 18193466 8637372 135630383 27032823 12505468 150627916 2582369 ...

output:

24 32 36 19 12 18 22 35 20 9 8 26 13 16 3 7 17 30 23 2 14 27 4 31 38

result:

ok OK (n = 38)

Test #26:

score: -100
Time Limit Exceeded

input:

40
1864672 53270952 1031984 2509194 87644337 5654703 35444518 97736603 4840437 55730665 64535977 101111649 9875388 4664481 144584267 8792304 117354393 23125256 32473404 39262639 22801665 117751347 11198973 27861810 6885619 46509857 106429773 38309950 102577045 69246894 25937400 2327839 121605468 155...

output:


result: