CSES - HIIT Open 2024

Submission details
Task:	Inheritance
Sender:	Tyämiesklubi
Submission time:	2024-11-16 15:44:22 +0200
Language:	C++ (C++20)
Status:	READY
Result:	TIME LIMIT EXCEEDED

Test results
test	verdict	time
#1	ACCEPTED	0.00 s	details
#2	ACCEPTED	0.00 s	details
#3	ACCEPTED	0.00 s	details
#4	ACCEPTED	0.00 s	details
#5	TIME LIMIT EXCEEDED	--	details
#6	TIME LIMIT EXCEEDED	--	details
#7	ACCEPTED	2.40 s	details
#8	TIME LIMIT EXCEEDED	--	details
#9	ACCEPTED	2.27 s	details
#10	ACCEPTED	2.25 s	details
#11	ACCEPTED	0.55 s	details
#12	WRONG ANSWER	2.74 s	details
#13	ACCEPTED	0.05 s	details
#14	WRONG ANSWER	2.85 s	details
#15	TIME LIMIT EXCEEDED	--	details
#16	TIME LIMIT EXCEEDED	--	details
#17	TIME LIMIT EXCEEDED	--	details
#18	TIME LIMIT EXCEEDED	--	details
#19	TIME LIMIT EXCEEDED	--	details
#20	TIME LIMIT EXCEEDED	--	details
#21	TIME LIMIT EXCEEDED	--	details
#22	TIME LIMIT EXCEEDED	--	details
#23	TIME LIMIT EXCEEDED	--	details
#24	TIME LIMIT EXCEEDED	--	details
#25	TIME LIMIT EXCEEDED	--	details
#26	TIME LIMIT EXCEEDED	--	details
#27	TIME LIMIT EXCEEDED	--	details
#28	ACCEPTED	2.36 s	details

Code

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

typedef long long ll;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    vector<ll> v(n);
    for(ll &i : v) cin >> i;

    random_shuffle(v.begin(), v.end());

    int m = n/2+1;

    unordered_set<ll> s;
    auto calc_set = [&](vector<ll> t){
        s.clear();
        s.insert(0);
        for(int i=0; i<(1<<t.size()); i++){
            ll sum = 0;
            for(int j=0; j<(int)t.size(); j++){
                if((i>>j)&1){
                    sum += t[j];
                }
            }
            s.insert(sum);
        }
    };

    vector<ll> ls, rs;
    for(int i=0; i<m; i++) ls.push_back(v[i]);
    for(int i=m; i<n; i++) rs.push_back(v[i]);

    calc_set(rs);

    auto mmiddle = [&](vector<ll> t, ll x){
        for(int i=0; i<(1<<t.size()); i++){
            ll sum = 0;
            for(int j=0; j<(int)t.size(); j++){
                if((i>>j)&1){
                    sum += t[j];
                }
            }
            if(s.find(x-sum) != s.end()){
                return i;
            }
        }
        return -1;
    };

    auto answer = [&](ll x, vector<ll> t, int ii, vector<ll> o){
        vector<ll> ans;
        ll osum = 0;
        for(int j=0; j<(int)t.size(); j++){
            if((ii>>j)&1){
                ans.push_back(t[j]);
                osum += t[j];
            }
        }
        for(int i=0; i<(1<<o.size()); i++){
            ll sum = 0;
            for(int j=0; j<(int)o.size(); j++){
                if((i>>j)&1){
                    sum += o[j];
                }
            }
            if(x-sum == osum){
                for(int j=0; j<(int)o.size(); j++){
                    if((i>>j)&1){
                        ans.push_back(o[j]);
                    }
                }
                break;
            }
        }
        cout << x << '\n';
        for(ll k : ans) cout << k << ' ';
        cout << '\n';
        exit(0);
    };

    for(int i=0; i<m; i++){
        vector<ll> t;
        for(int j=0; j<m; j++) if(j != i) t.push_back(v[j]);
        int ii = mmiddle(t, v[i]);
        if(ii != -1) answer(v[i], t, ii, rs);
    }

    calc_set(ls);
    
    for(int i=m; i<n; i++){
        vector<ll> t;
        for(int j=m; j<n; j++) if(j != i) t.push_back(v[j]);
        int ii = mmiddle(t, v[i]);
        if(ii != -1) answer(v[i], t, ii, ls);
    }
}

Test details

Test 1

Verdict: ACCEPTED

input
`2 1 1` view save

correct output
`1 1` view save

user output
`1 1` view save

Test 2

Verdict: ACCEPTED

input
`3 1 2 3` view save

correct output
`3 1 2` view save

user output
`3 1 2` view save

Test 3

Verdict: ACCEPTED

input
`3 2 2 2` view save

correct output
`2 2` view save

user output
`2 2` view save

Test 4

Verdict: ACCEPTED

input
`6 3 2 5 1 7 8` view save

correct output
`2 1 3` view save

user output
`7 2 5` view save

Test 5

Verdict: TIME LIMIT EXCEEDED

input
`40 27487790693 27487790692 274877...` view save

correct output
`27487790651 27487774282 27487790652 27487774281` view save

user output
(empty)

Test 6

Verdict: TIME LIMIT EXCEEDED

input
`40 27487790693 27487790692 274877...` view save

correct output
`27487790688 27487790486 274877...` view save

user output
(empty)

Test 7

Verdict: ACCEPTED

input
`40 1 2 4 8 16 32 64 128 256 512 1...` view save

correct output
`549755813887 1 2 4 8 16 32 64 128 256 512 1...` view save

user output
`549755813887 16 268435456 2048 32768 167772...` view save

Test 8

Verdict: TIME LIMIT EXCEEDED

input
`40 1 2 4 8 16 32 64 128 256 512 1...` view save

correct output
`274877906943 1 2 4 8 16 32 64 128 256 512 1...` view save

user output
(empty)

Test 9

Verdict: ACCEPTED

input
`40 1 3 7 15 31 63 127 255 511 102...` view save

correct output
`1 7 31 2047 4095 68719476735 2...` view save

user output
`374877906968 68719476735 262143 134217727 4...` view save

Test 10

Verdict: ACCEPTED

input
`40 1 3 5 10 20 40 80 160 320 640 ...` view save

correct output
`5 40 80 640 1280 10240 20480 1...` view save

user output
`412316860415 2560 40960 42949672960 8388608...` view save

Test 11

Verdict: ACCEPTED

input
`40 642081522561 67331511756 17915...` view save

correct output
`10000000008 10000000005 10000000007 10000000006` view save

user output
`10000000018 10000000018` view save

Test 12

Verdict: WRONG ANSWER

input
`40 27487790739 27487790734 274877...` view save

correct output
`27487790739 27487790701 274877...` view save

user output
(empty)

Test 13

Verdict: ACCEPTED

input
`40 27487790726 27487790723 274877...` view save

correct output
`27487790681 27487790678 27487790680 27487790679` view save

user output
`27487790723 27487790723` view save

Test 14

Verdict: WRONG ANSWER

input
`40 27487790744 27487790715 274877...` view save

correct output
`27487790711 27487790710 274877...` view save

user output
(empty)

Test 15

Verdict: TIME LIMIT EXCEEDED

input
`40 19669566523 16528665765 196239...` view save

correct output
`16528665765 10929136447 125755...` view save

user output
(empty)

Test 16

Verdict: TIME LIMIT EXCEEDED

input
`40 18103769567 14444217460 183355...` view save

correct output
`15982577206 17769110557 124644...` view save

user output
(empty)

Test 17

Verdict: TIME LIMIT EXCEEDED

input
`40 17856614174 19048069863 175427...` view save

correct output
`17563061793 16010946154 132865...` view save

user output
(empty)

Test 18

Verdict: TIME LIMIT EXCEEDED

input
`40 1786812 2068856 1749503 168298...` view save

correct output
`2068856 2090472 1725454 169431...` view save

user output
(empty)

Test 19

Verdict: TIME LIMIT EXCEEDED

input
`40 1129650 1662217 1678779 182047...` view save

correct output
`1820473 1456513 1939701 160831...` view save

user output
(empty)

Test 20

Verdict: TIME LIMIT EXCEEDED

input
`40 24808689091 27070970684 226856...` view save

correct output
`22685667072 25049152240 183404...` view save

user output
(empty)

Test 21

Verdict: TIME LIMIT EXCEEDED

input
`40 16712721711 16122645964 169234...` view save

correct output
`25590302248 25776083681 200636...` view save

user output
(empty)

Test 22

Verdict: TIME LIMIT EXCEEDED

input
`40 27016877723 26624688594 255882...` view save

correct output
`18637668548 14215273154 231053...` view save

user output
(empty)

Test 23

Verdict: TIME LIMIT EXCEEDED

input
`40 22612801338 17987950258 220495...` view save

correct output
`22612801338 28914153399 201796...` view save

user output
(empty)

Test 24

Verdict: TIME LIMIT EXCEEDED

input
`40 23397776706 18089114838 194902...` view save

correct output
`17041900579 24486781810 275051...` view save

user output
(empty)

Test 25

Verdict: TIME LIMIT EXCEEDED

input
`40 24840659504 32664220268 190864...` view save

correct output
`32664220268 19086427470 240084...` view save

user output
(empty)

Test 26

Verdict: TIME LIMIT EXCEEDED

input
`40 22577006557 25490929450 308237...` view save

correct output
`22577006557 33714917325 183357...` view save

user output
(empty)

Test 27

Verdict: TIME LIMIT EXCEEDED

input
`40 25196082534 25787578777 336717...` view save

correct output
`20236894598 25724569573 318791...` view save

user output
(empty)

Test 28

Verdict: ACCEPTED

input
`40 5000000000 5000000001 50000000...` view save

correct output
`5000000002 5000000594 50000022...` view save

user output
`136573282068 5065679652 5000008807 50000343...` view save

HIIT Open 2024

Inheritance

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Tasks

Submissions (Tyämiesklubi)