CSES - HIIT Open 2019 - Results
Submission details
Task:Epic Subset
Sender:Varokaa J:tä
Submission time:2019-05-25 14:53:55 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.01 sdetails
#2ACCEPTED0.02 sdetails
#3ACCEPTED0.02 sdetails
#4ACCEPTED0.01 sdetails
#5ACCEPTED0.02 sdetails
#6ACCEPTED0.03 sdetails
#7ACCEPTED0.02 sdetails
#8ACCEPTED0.02 sdetails
#9ACCEPTED0.02 sdetails
#10ACCEPTED0.02 sdetails
#11ACCEPTED0.03 sdetails
#12ACCEPTED0.02 sdetails
#13ACCEPTED0.02 sdetails
#14ACCEPTED0.01 sdetails
#15ACCEPTED0.02 sdetails
#16ACCEPTED0.03 sdetails
#17ACCEPTED0.03 sdetails
#18ACCEPTED0.02 sdetails
#19ACCEPTED0.02 sdetails
#20ACCEPTED0.01 sdetails
#21ACCEPTED0.01 sdetails
#22ACCEPTED0.02 sdetails
#23ACCEPTED0.02 sdetails
#24ACCEPTED0.03 sdetails
#25ACCEPTED0.03 sdetails
#26ACCEPTED0.01 sdetails
#27ACCEPTED0.02 sdetails
#28ACCEPTED0.02 sdetails
#29ACCEPTED0.02 sdetails
#30ACCEPTED0.02 sdetails
#31ACCEPTED0.04 sdetails
#32ACCEPTED0.01 sdetails
#33ACCEPTED0.02 sdetails
#34ACCEPTED0.02 sdetails
#35ACCEPTED0.04 sdetails
#36ACCEPTED0.02 sdetails
#37ACCEPTED0.01 sdetails
#38ACCEPTED0.03 sdetails
#39ACCEPTED0.03 sdetails
#40ACCEPTED0.02 sdetails
#41ACCEPTED0.01 sdetails
#42ACCEPTED0.01 sdetails
#43ACCEPTED0.01 sdetails
#44ACCEPTED0.03 sdetails
#45ACCEPTED0.02 sdetails
#46ACCEPTED0.02 sdetails
#47ACCEPTED0.01 sdetails
#48ACCEPTED0.02 sdetails
#49ACCEPTED0.01 sdetails
#50ACCEPTED0.01 sdetails
#51ACCEPTED0.02 sdetails
#52ACCEPTED0.02 sdetails
#53ACCEPTED0.03 sdetails
#54ACCEPTED0.03 sdetails
#55ACCEPTED0.01 sdetails
#56ACCEPTED0.04 sdetails
#57ACCEPTED0.03 sdetails
#58ACCEPTED0.02 sdetails
#59ACCEPTED0.02 sdetails
#60ACCEPTED0.02 sdetails
#61ACCEPTED0.02 sdetails
#62ACCEPTED0.01 sdetails
#63ACCEPTED0.01 sdetails
#64ACCEPTED0.01 sdetails
#65ACCEPTED0.03 sdetails
#66ACCEPTED0.02 sdetails
#67ACCEPTED0.01 sdetails
#68ACCEPTED0.03 sdetails
#69ACCEPTED0.02 sdetails
#70ACCEPTED0.02 sdetails
#71ACCEPTED0.01 sdetails
#72ACCEPTED0.01 sdetails
#73ACCEPTED0.02 sdetails
#74ACCEPTED0.02 sdetails
#75ACCEPTED0.01 sdetails
#76ACCEPTED0.02 sdetails
#77ACCEPTED0.02 sdetails
#78ACCEPTED0.01 sdetails
#79ACCEPTED0.01 sdetails
#80ACCEPTED0.02 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:52:8: warning: unused variable 'res' [-Wunused-variable]
     ll res = 0;
        ^~~

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

vector<int> nums;
int used[10000];
vector<int> tulos;


int dfs(int i, int maxi) {
    for (int n : nums) {
        if (used[n + i]) return false;
    }
    for (int n : nums) used[n + i]++;
    nums.push_back(i);
    if (nums.size() > tulos.size() || (nums.size() == tulos.size() && nums.back() < tulos.back())) {
        tulos = nums;
        for (int a : tulos) cout << a << " ";
        cout << endl;
    }
    int best = 0;
    for (int j = i+1; j <= maxi; j++) {
        int t = dfs(j, maxi);
        if (t > best) best = t;
    }
    nums.pop_back();
    for (int n : nums) used[n + i]--;
    return best;
}

int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll n;
    cin >> n;
    if (n >= 72) cout << "12\n1 2 3 8 13 23 38 41 55 64 68 72\n";
    else if (n >= 58) cout << "11\n1 2 6 10 18 32 34 45 52 55 58\n";
    else if (n >= 46) cout << "10\n1 2 8 11 14 22 27 42 44 46\n";
    else if (n >= 35) cout << "9\n1 2 3 5 9 16 25 30 35\n";
    else if (n >= 25) cout << "8\n1 2 3 5 9 15 20 25\n";
    else if (n >= 19) cout << "7\n1 2 3 5 9 14 19 \n";
    else if (n >= 13) cout << "6\n1 2 3 5 8 13\n";
    else if (n >= 8) cout << "5\n1 2 3 5 8\n";
    else if (n >= 5) cout << "4\n1 2 3 5\n";
    else if (n >= 3) cout << "3\n1 2 3\n";
    else if (n >= 2) cout << "2\n1 2\n";
    else if (n >= 1) cout << "1\n1\n";
    //cout << dfs(1, n) << endl;
    return 0;
    
    ll res = 0;
    ll best = 0;
    
    for (ll i = 0b00010111; i < (1ll<<n); i += 0b100000000) {
        for (int a = 0; a < n; a++) {
            if (!((i >> a) & 1)) continue;
            for (int b = a+1; b < n; b++) {
                if (!((i >> b) & 1)) continue;
                for (int c = b+1; c < n; c++) {
                    if (!((i >> c) & 1)) continue;
                    for (int d = c+1; d < n; d++) {
                        if (!((i >> d) & 1)) continue;
                        if (a + c == b + d || a + d == b + c) goto fail;
                    }
                }
            }
        }
        if (__builtin_popcountll(i) > __builtin_popcountll(best)) best = i;
        fail:;
    }
    cout << __builtin_popcountll(best) << endl;
    for (int a = 0; a < n; a++) {
        if (!((best >> a) & 1)) continue;
        cout << a+1 << " ";
    }
    cout << endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
1

correct output
1
1

user output
1
1

Test 2

Verdict: ACCEPTED

input
2

correct output
2
1 2 

user output
2
1 2

Test 3

Verdict: ACCEPTED

input
3

correct output
3
1 2 3 

user output
3
1 2 3

Test 4

Verdict: ACCEPTED

input
4

correct output
3
1 3 4 

user output
3
1 2 3

Test 5

Verdict: ACCEPTED

input
5

correct output
4
1 3 4 5 

user output
4
1 2 3 5

Test 6

Verdict: ACCEPTED

input
6

correct output
4
1 3 5 6 

user output
4
1 2 3 5

Test 7

Verdict: ACCEPTED

input
7

correct output
4
1 3 6 7 

user output
4
1 2 3 5

Test 8

Verdict: ACCEPTED

input
8

correct output
5
1 4 6 7 8 

user output
5
1 2 3 5 8

Test 9

Verdict: ACCEPTED

input
9

correct output
5
1 3 5 8 9 

user output
5
1 2 3 5 8

Test 10

Verdict: ACCEPTED

input
10

correct output
5
1 3 5 9 10 

user output
5
1 2 3 5 8

Test 11

Verdict: ACCEPTED

input
11

correct output
5
1 3 5 10 11 

user output
5
1 2 3 5 8

Test 12

Verdict: ACCEPTED

input
12

correct output
5
1 3 5 11 12 

user output
5
1 2 3 5 8

Test 13

Verdict: ACCEPTED

input
13

correct output
6
1 4 7 11 12 13 

user output
6
1 2 3 5 8 13

Test 14

Verdict: ACCEPTED

input
14

correct output
6
1 3 5 8 13 14 

user output
6
1 2 3 5 8 13

Test 15

Verdict: ACCEPTED

input
15

correct output
6
1 3 5 8 14 15 

user output
6
1 2 3 5 8 13

Test 16

Verdict: ACCEPTED

input
16

correct output
6
1 3 5 8 15 16 

user output
6
1 2 3 5 8 13

Test 17

Verdict: ACCEPTED

input
17

correct output
6
1 3 5 8 16 17 

user output
6
1 2 3 5 8 13

Test 18

Verdict: ACCEPTED

input
18

correct output
6
1 3 5 8 17 18 

user output
6
1 2 3 5 8 13

Test 19

Verdict: ACCEPTED

input
19

correct output
7
1 5 9 12 17 18 19 

user output
7
1 2 3 5 9 14 19 

Test 20

Verdict: ACCEPTED

input
20

correct output
7
1 3 5 8 11 19 20 

user output
7
1 2 3 5 9 14 19 

Test 21

Verdict: ACCEPTED

input
21

correct output
7
1 3 5 8 11 20 21 

user output
7
1 2 3 5 9 14 19 

Test 22

Verdict: ACCEPTED

input
22

correct output
7
1 3 5 8 11 21 22 

user output
7
1 2 3 5 9 14 19 

Test 23

Verdict: ACCEPTED

input
23

correct output
7
1 3 5 8 11 22 23 

user output
7
1 2 3 5 9 14 19 

Test 24

Verdict: ACCEPTED

input
24

correct output
7
1 3 5 8 11 23 24 

user output
7
1 2 3 5 9 14 19 

Test 25

Verdict: ACCEPTED

input
25

correct output
8
1 6 11 17 21 23 24 25 

user output
8
1 2 3 5 9 15 20 25

Test 26

Verdict: ACCEPTED

input
26

correct output
8
1 6 11 18 22 24 25 26 

user output
8
1 2 3 5 9 15 20 25

Test 27

Verdict: ACCEPTED

input
27

correct output
8
1 5 7 9 12 17 26 27 

user output
8
1 2 3 5 9 15 20 25

Test 28

Verdict: ACCEPTED

input
28

correct output
8
1 3 5 9 12 15 27 28 

user output
8
1 2 3 5 9 15 20 25

Test 29

Verdict: ACCEPTED

input
29

correct output
8
1 3 5 9 12 15 28 29 

user output
8
1 2 3 5 9 15 20 25

Test 30

Verdict: ACCEPTED

input
30

correct output
8
1 3 5 9 12 15 29 30 

user output
8
1 2 3 5 9 15 20 25

Test 31

Verdict: ACCEPTED

input
31

correct output
8
1 3 5 9 12 15 30 31 

user output
8
1 2 3 5 9 15 20 25

Test 32

Verdict: ACCEPTED

input
32

correct output
8
1 3 5 9 12 15 31 32 

user output
8
1 2 3 5 9 15 20 25

Test 33

Verdict: ACCEPTED

input
33

correct output
8
1 3 5 9 12 15 32 33 

user output
8
1 2 3 5 9 15 20 25

Test 34

Verdict: ACCEPTED

input
34

correct output
8
1 3 5 9 12 15 33 34 

user output
8
1 2 3 5 9 15 20 25

Test 35

Verdict: ACCEPTED

input
35

correct output
9
1 5 8 11 16 21 33 34 35 

user output
9
1 2 3 5 9 16 25 30 35

Test 36

Verdict: ACCEPTED

input
36

correct output
9
1 6 11 21 23 29 32 35 36 

user output
9
1 2 3 5 9 16 25 30 35

Test 37

Verdict: ACCEPTED

input
37

correct output
9
1 3 7 10 13 18 23 36 37 

user output
9
1 2 3 5 9 16 25 30 35

Test 38

Verdict: ACCEPTED

input
38

correct output
9
2 4 8 11 14 19 24 37 38 

user output
9
1 2 3 5 9 16 25 30 35

Test 39

Verdict: ACCEPTED

input
39

correct output
9
1 6 8 10 16 19 22 38 39 

user output
9
1 2 3 5 9 16 25 30 35

Test 40

Verdict: ACCEPTED

input
40

correct output
9
1 3 5 10 15 18 21 39 40 

user output
9
1 2 3 5 9 16 25 30 35

Test 41

Verdict: ACCEPTED

input
41

correct output
9
1 3 5 10 15 18 21 40 41 

user output
9
1 2 3 5 9 16 25 30 35

Test 42

Verdict: ACCEPTED

input
42

correct output
9
1 3 5 10 15 18 21 41 42 

user output
9
1 2 3 5 9 16 25 30 35

Test 43

Verdict: ACCEPTED

input
43

correct output
9
1 3 5 10 15 18 21 42 43 

user output
9
1 2 3 5 9 16 25 30 35

Test 44

Verdict: ACCEPTED

input
44

correct output
9
1 3 5 10 15 18 21 43 44 

user output
9
1 2 3 5 9 16 25 30 35

Test 45

Verdict: ACCEPTED

input
45

correct output
9
1 3 5 10 15 18 21 44 45 

user output
9
1 2 3 5 9 16 25 30 35

Test 46

Verdict: ACCEPTED

input
46

correct output
10
1 3 5 20 25 33 36 39 45 46 

user output
10
1 2 8 11 14 22 27 42 44 46

Test 47

Verdict: ACCEPTED

input
47

correct output
10
2 4 6 21 26 34 37 40 46 47 

user output
10
1 2 8 11 14 22 27 42 44 46

Test 48

Verdict: ACCEPTED

input
48

correct output
10
1 3 5 9 12 15 25 30 47 48 

user output
10
1 2 8 11 14 22 27 42 44 46

Test 49

Verdict: ACCEPTED

input
49

correct output
10
1 3 5 9 14 19 26 29 48 49 

user output
10
1 2 8 11 14 22 27 42 44 46

Test 50

Verdict: ACCEPTED

input
50

correct output
10
2 4 6 10 15 20 27 30 49 50 

user output
10
1 2 8 11 14 22 27 42 44 46

Test 51

Verdict: ACCEPTED

input
51

correct output
10
3 5 7 11 16 21 28 31 50 51 

user output
10
1 2 8 11 14 22 27 42 44 46

Test 52

Verdict: ACCEPTED

input
52

correct output
10
1 4 7 11 13 15 26 31 51 52 

user output
10
1 2 8 11 14 22 27 42 44 46

Test 53

Verdict: ACCEPTED

input
53

correct output
10
1 4 8 10 12 20 25 30 52 53 

user output
10
1 2 8 11 14 22 27 42 44 46

Test 54

Verdict: ACCEPTED

input
54

correct output
10
1 3 5 9 12 19 24 29 53 54 

user output
10
1 2 8 11 14 22 27 42 44 46

Test 55

Verdict: ACCEPTED

input
55

correct output
10
1 3 5 9 12 19 24 29 54 55 

user output
10
1 2 8 11 14 22 27 42 44 46

Test 56

Verdict: ACCEPTED

input
56

correct output
10
1 3 5 9 12 19 24 29 55 56 

user output
10
1 2 8 11 14 22 27 42 44 46

Test 57

Verdict: ACCEPTED

input
57

correct output
10
1 3 5 9 12 19 24 29 56 57 

user output
10
1 2 8 11 14 22 27 42 44 46

Test 58

Verdict: ACCEPTED

input
58

correct output
11
1 3 14 21 24 27 41 49 53 57 58...

user output
11
1 2 6 10 18 32 34 45 52 55 58

Test 59

Verdict: ACCEPTED

input
59

correct output
11
1 5 7 9 23 34 39 46 49 58 59 

user output
11
1 2 6 10 18 32 34 45 52 55 58

Test 60

Verdict: ACCEPTED

input
60

correct output
11
1 3 5 9 27 32 39 46 49 59 60 

user output
11
1 2 6 10 18 32 34 45 52 55 58

Test 61

Verdict: ACCEPTED

input
61

correct output
11
1 7 9 13 17 24 33 42 47 60 61 

user output
11
1 2 6 10 18 32 34 45 52 55 58

Test 62

Verdict: ACCEPTED

input
62

correct output
11
1 3 5 9 14 23 35 38 45 61 62 

user output
11
1 2 6 10 18 32 34 45 52 55 58

Test 63

Verdict: ACCEPTED

input
63

correct output
11
2 4 6 10 15 24 36 39 46 62 63 

user output
11
1 2 6 10 18 32 34 45 52 55 58

Test 64

Verdict: ACCEPTED

input
64

correct output
11
1 3 5 9 17 28 33 43 46 63 64 

user output
11
1 2 6 10 18 32 34 45 52 55 58

Test 65

Verdict: ACCEPTED

input
65

correct output
11
1 5 7 9 16 21 33 43 46 64 65 

user output
11
1 2 6 10 18 32 34 45 52 55 58

Test 66

Verdict: ACCEPTED

input
66

correct output
11
1 4 10 15 20 22 35 39 43 65 66...

user output
11
1 2 6 10 18 32 34 45 52 55 58

Test 67

Verdict: ACCEPTED

input
67

correct output
11
1 3 5 9 15 18 25 36 41 66 67 

user output
11
1 2 6 10 18 32 34 45 52 55 58

Test 68

Verdict: ACCEPTED

input
68

correct output
11
1 4 6 11 18 22 26 35 41 67 68 

user output
11
1 2 6 10 18 32 34 45 52 55 58

Test 69

Verdict: ACCEPTED

input
69

correct output
11
1 3 5 11 16 21 28 37 40 68 69 

user output
11
1 2 6 10 18 32 34 45 52 55 58

Test 70

Verdict: ACCEPTED

input
70

correct output
11
1 5 7 9 18 23 28 35 38 69 70 

user output
11
1 2 6 10 18 32 34 45 52 55 58

Test 71

Verdict: ACCEPTED

input
71

correct output
11
1 5 7 9 18 23 28 35 38 70 71 

user output
11
1 2 6 10 18 32 34 45 52 55 58

Test 72

Verdict: ACCEPTED

input
72

correct output
12
1 3 5 9 17 31 36 51 54 61 71 7...

user output
12
1 2 3 8 13 23 38 41 55 64 68 7...

Test 73

Verdict: ACCEPTED

input
73

correct output
12
2 4 6 10 18 32 37 52 55 62 72 ...

user output
12
1 2 3 8 13 23 38 41 55 64 68 7...

Test 74

Verdict: ACCEPTED

input
74

correct output
12
3 5 7 11 19 33 38 53 56 63 73 ...

user output
12
1 2 3 8 13 23 38 41 55 64 68 7...

Test 75

Verdict: ACCEPTED

input
75

correct output
12
1 4 7 13 27 32 40 53 57 64 74 ...

user output
12
1 2 3 8 13 23 38 41 55 64 68 7...

Test 76

Verdict: ACCEPTED

input
76

correct output
12
1 3 5 9 18 33 38 54 57 64 75 7...

user output
12
1 2 3 8 13 23 38 41 55 64 68 7...

Test 77

Verdict: ACCEPTED

input
77

correct output
12
1 3 5 11 21 32 39 51 54 63 76 ...

user output
12
1 2 3 8 13 23 38 41 55 64 68 7...

Test 78

Verdict: ACCEPTED

input
78

correct output
12
1 3 5 9 12 15 27 40 45 61 77 7...

user output
12
1 2 3 8 13 23 38 41 55 64 68 7...

Test 79

Verdict: ACCEPTED

input
79

correct output
12
1 3 5 9 15 18 27 43 48 59 78 7...

user output
12
1 2 3 8 13 23 38 41 55 64 68 7...

Test 80

Verdict: ACCEPTED

input
80

correct output
12
1 5 9 12 17 19 29 38 44 57 79 ...

user output
12
1 2 3 8 13 23 38 41 55 64 68 7...