CSES - Datatähti 2019 loppu - Results
Submission details
Task:Binääripuu
Sender:Roope Salmi
Submission time:2019-01-17 12:57:24 +0200
Language:C++
Status:READY
Result:26
Feedback
groupverdictscore
#10
#2ACCEPTED26
#30
Test results
testverdicttimegroup
#10.02 s1details
#2ACCEPTED0.01 s1details
#30.03 s1details
#40.02 s1details
#50.02 s1details
#6ACCEPTED0.01 s1details
#70.02 s1details
#80.01 s1details
#90.03 s1details
#100.03 s1details
#110.02 s1details
#120.02 s1details
#130.01 s1details
#140.03 s1details
#150.02 s1details
#160.02 s1details
#170.03 s1details
#180.02 s1details
#190.02 s1details
#200.01 s1details
#210.02 s1details
#220.02 s1details
#23ACCEPTED0.02 s1details
#240.02 s1details
#250.02 s1details
#260.02 s1details
#270.02 s1details
#280.01 s1details
#290.01 s1details
#300.02 s1details
#310.01 s1details
#320.02 s1details
#330.02 s1details
#34ACCEPTED0.01 s1details
#350.01 s1details
#36ACCEPTED0.01 s2details
#37ACCEPTED0.03 s2details
#38ACCEPTED0.02 s2details
#39ACCEPTED0.01 s2details
#40ACCEPTED0.02 s2details
#41ACCEPTED0.02 s2details
#42ACCEPTED0.02 s2details
#43ACCEPTED0.01 s2details
#44ACCEPTED0.01 s2details
#45ACCEPTED0.02 s2details
#46ACCEPTED0.01 s3details
#470.02 s3details
#480.03 s3details
#490.01 s3details
#50ACCEPTED0.03 s3details
#51ACCEPTED0.01 s3details
#520.02 s3details
#530.02 s3details
#540.02 s3details
#550.33 s3details
#560.33 s3details
#570.33 s3details
#580.33 s3details
#590.33 s3details
#600.30 s3details
#610.07 s3details
#620.33 s3details
#630.04 s3details
#640.33 s3details
#650.07 s3details
#660.30 s3details
#67ACCEPTED0.01 s3details
#680.02 s3details
#690.02 s3details
#700.03 s3details
#710.01 s3details
#720.03 s3details
#730.02 s3details
#740.02 s3details
#750.01 s3details
#760.01 s3details
#770.02 s3details

Code

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
const long M = 1e9+7;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  long t[m];
  for (int i = 0; i < m; ++i) cin >> t[i];
  sort(t, t+m);
  set<long> x;
  long lvc[2] = {(1l<<(n-2))%M, (1l<<(n-2))%M};
  for (int i = 0; i < m; ++i) {
    bool f = 1;
    int bits = 0;
    for (long c = t[i]; c; c >>= 1) {
      bits++;
      if (x.count(c)) {
	f = 0;
	break;
      }
    }
    if (f) {
      x.insert(t[i]);
      cout << t[i] << " " << bits << " " << (1l<<(n-bits)) << endl;
      lvc[(t[i] >> (bits-2))&1] += M-(1l<<(n-bits))%M;
      lvc[(t[i] >> (bits-2))&1] %= M;
    }
  }
  cout << lvc[0]*lvc[1]*2%M << endl;
}

Test details

Test 1

Group: 1

Verdict:

input
4 3
10
5
13

correct output
12

user output
5 3 2
13 4 1
12

Test 2

Group: 1

Verdict: ACCEPTED

input
2 0

correct output
2

user output
2

Test 3

Group: 1

Verdict:

input
2 1
2

correct output
0

user output
2 2 1
0

Test 4

Group: 1

Verdict:

input
2 1
3

correct output
0

user output
3 2 1
0

Test 5

Group: 1

Verdict:

input
2 2
2
3

correct output
0

user output
2 2 1
3 2 1
0

Test 6

Group: 1

Verdict: ACCEPTED

input
6 0

correct output
512

user output
512

Test 7

Group: 1

Verdict:

input
6 1
29

correct output
448

user output
29 5 2
448

Test 8

Group: 1

Verdict:

input
6 1
63

correct output
480

user output
63 6 1
480

Test 9

Group: 1

Verdict:

input
6 10
50
63
56
5
...

correct output
132

user output
5 3 8
18 5 2
48 6 1
50 6 1
56 6 1
...

Test 10

Group: 1

Verdict:

input
6 10
25
57
62
42
...

correct output
162

user output
16 5 2
22 5 2
25 5 2
26 5 2
34 6 1
...

Test 11

Group: 1

Verdict:

input
6 10
14
26
34
42
...

correct output
126

user output
5 3 8
14 4 4
26 5 2
34 6 1
62 6 1
...

Test 12

Group: 1

Verdict:

input
6 10
21
60
23
59
...

correct output
128

user output
11 4 4
13 4 4
21 5 2
34 6 1
35 6 1
...

Test 13

Group: 1

Verdict:

input
6 10
8
30
32
16
...

correct output
0

user output
2 2 16
27 5 2
30 5 2
62 6 1
0

Test 14

Group: 1

Verdict:

input
6 20
46
39
55
24
...

correct output
48

user output
10 4 4
11 4 4
12 4 4
15 4 4
27 5 2
...

Test 15

Group: 1

Verdict:

input
6 25
36
23
27
33
...

correct output
4

user output
4 3 8
7 3 8
11 4 4
13 4 4
20 5 2
...

Test 16

Group: 1

Verdict:

input
6 62
42
11
4
61
...

correct output
0

user output
2 2 16
3 2 16
0

Test 17

Group: 1

Verdict:

input
6 32
62
38
57
35
...

correct output
0

user output
32 6 1
33 6 1
34 6 1
35 6 1
36 6 1
...

Test 18

Group: 1

Verdict:

input
6 21
38
51
47
35
...

correct output
60

user output
32 6 1
35 6 1
37 6 1
38 6 1
40 6 1
...

Test 19

Group: 1

Verdict:

input
6 31
59
15
3
26
...

correct output
0

user output
3 2 16
0

Test 20

Group: 1

Verdict:

input
6 14
13
53
55
26
...

correct output
256

user output
6 3 8
256

Test 21

Group: 1

Verdict:

input
5 10
5
17
21
7
...

correct output
6

user output
5 3 4
7 3 4
17 5 1
24 5 1
25 5 1
...

Test 22

Group: 1

Verdict:

input
6 5
38
18
31
44
...

correct output
312

user output
18 5 2
31 5 2
38 6 1
44 6 1
61 6 1
...

Test 23

Group: 1

Verdict: ACCEPTED

input
3 0

correct output
8

user output
8

Test 24

Group: 1

Verdict:

input
3 1
2

correct output
0

user output
2 2 2
0

Test 25

Group: 1

Verdict:

input
3 1
3

correct output
0

user output
3 2 2
0

Test 26

Group: 1

Verdict:

input
3 2
4
6

correct output
2

user output
4 3 1
6 3 1
2

Test 27

Group: 1

Verdict:

input
3 2
4
7

correct output
2

user output
4 3 1
7 3 1
2

Test 28

Group: 1

Verdict:

input
3 2
5
6

correct output
2

user output
5 3 1
6 3 1
2

Test 29

Group: 1

Verdict:

input
3 2
5
7

correct output
2

user output
5 3 1
7 3 1
2

Test 30

Group: 1

Verdict:

input
3 2
3
6

correct output
0

user output
3 2 2
0

Test 31

Group: 1

Verdict:

input
3 3
4
5
6

correct output
0

user output
4 3 1
5 3 1
6 3 1
0

Test 32

Group: 1

Verdict:

input
3 3
4
6
7

correct output
0

user output
4 3 1
6 3 1
7 3 1
0

Test 33

Group: 1

Verdict:

input
3 4
4
5
6
7

correct output
0

user output
4 3 1
5 3 1
6 3 1
7 3 1
0

Test 34

Group: 1

Verdict: ACCEPTED

input
5 0

correct output
128

user output
128

Test 35

Group: 1

Verdict:

input
5 1
14

correct output
96

user output
14 4 2
96

Test 36

Group: 2

Verdict: ACCEPTED

input
2 0

correct output
2

user output
2

Test 37

Group: 2

Verdict: ACCEPTED

input
3 0

correct output
8

user output
8

Test 38

Group: 2

Verdict: ACCEPTED

input
4 0

correct output
32

user output
32

Test 39

Group: 2

Verdict: ACCEPTED

input
23 0

correct output
92960636

user output
92960636

Test 40

Group: 2

Verdict: ACCEPTED

input
36 0

correct output
635008130

user output
635008130

Test 41

Group: 2

Verdict: ACCEPTED

input
42 0

correct output
993282280

user output
993282280

Test 42

Group: 2

Verdict: ACCEPTED

input
57 0

correct output
608377687

user output
608377687

Test 43

Group: 2

Verdict: ACCEPTED

input
58 0

correct output
433510734

user output
433510734

Test 44

Group: 2

Verdict: ACCEPTED

input
59 0

correct output
734042929

user output
734042929

Test 45

Group: 2

Verdict: ACCEPTED

input
60 0

correct output
936171702

user output
936171702

Test 46

Group: 3

Verdict: ACCEPTED

input
2 0

correct output
2

user output
2

Test 47

Group: 3

Verdict:

input
2 1
2

correct output
0

user output
2 2 1
0

Test 48

Group: 3

Verdict:

input
2 1
3

correct output
0

user output
3 2 1
0

Test 49

Group: 3

Verdict:

input
2 2
2
3

correct output
0

user output
2 2 1
3 2 1
0

Test 50

Group: 3

Verdict: ACCEPTED

input
59 0

correct output
734042929

user output
734042929

Test 51

Group: 3

Verdict: ACCEPTED

input
60 0

correct output
936171702

user output
936171702

Test 52

Group: 3

Verdict:

input
60 1
2

correct output
0

user output
2 2 288230376151711744
0

Test 53

Group: 3

Verdict:

input
60 1
576460752303423487

correct output
399775198

user output
576460752303423487 59 2
399775198

Test 54

Group: 3

Verdict:

input
60 1
1152921504606846975

correct output
667973450

user output
1152921504606846975 60 1
667973450

Test 55

Group: 3

Verdict:

input
60 100000
793144025126277478
493960657696318193
320344157019848454
997683950258055349
...

correct output
12813436

user output
10627238995021 44 65536
18016018239554 45 32768
20840493737371 45 32768
37616681635432 46 16384
38507577331678 46 16384
...

Test 56

Group: 3

Verdict:

input
60 100000
986789393060040220
494066507202684187
290830182157570659
210871095549437400
...

correct output
95910570

user output
16034183462491 44 65536
57893425701277 46 16384
63631897254626 46 16384
90577439530378 47 8192
97639766273958 47 8192
...

Test 57

Group: 3

Verdict:

input
60 100000
562299894758506682
731132428235172865
481500339045425690
208947005967360560
...

correct output
331624281

user output
7014821912901 43 131072
10977096920815 44 65536
11790851036703 44 65536
16313806427959 44 65536
24443155556271 45 32768
...

Test 58

Group: 3

Verdict:

input
60 100000
257846911019866261
803021202233459674
658685893766403373
874237705485665885
...

correct output
880725152

user output
238070700988 38 4194304
30494002583094 45 32768
65382915042283 46 16384
91583672363036 47 8192
92197932285919 47 8192
...

Test 59

Group: 3

Verdict:

input
60 100000
681388061028265547
990382999862855868
290694941402209648
491574111397234946
...

correct output
768320742

user output
26065615602100 45 32768
26514152026765 45 32768
35393316810045 46 16384
36027322342167 46 16384
43561414652738 46 16384
...

Test 60

Group: 3

Verdict:

input
60 100000
816968727394104576
879176301780517486
1075817811951859004
632046213104404023
...

correct output
111155168

user output
576465706122888777 60 1
576467385086079123 60 1
576471379542418503 60 1
576472607760740400 60 1
576478768321663026 60 1
...

Test 61

Group: 3

Verdict:

input
60 100000
406817930303406656
101704482575856800
406817930303412346
813635860606874021
...

correct output
295651662

user output
12415097970685 44 65536
295651662

Test 62

Group: 3

Verdict:

input
59 100000
234885934259928845
244746379456935555
40048493361902167
530369614866009610
...

correct output
78892926

user output
6051393097757 43 65536
25282689674435 45 16384
28263077276156 45 16384
33595045590121 45 16384
35723785116248 46 8192
...

Test 63

Group: 3

Verdict:

input
16 65534
26355
15205
3420
22822
...

correct output
0

user output
2 2 16384
3 2 16384
0

Test 64

Group: 3

Verdict:

input
60 99999
1030879879260090869
925369330408563145
403438777989811739
321883235203598800
...

correct output
596899803

user output
2379051592350 42 262144
5967373309128 43 131072
8114697003106 43 131072
29112527788213 45 32768
46237207700058 46 16384
...

Test 65

Group: 3

Verdict:

input
60 100000
418885324976523921
418885324976523063
837770649953084829
104721331244134167
...

correct output
0

user output
2 2 288230376151711744
0

Test 66

Group: 3

Verdict:

input
43 100000
5497882741157
4163319796881
3705445016042
8647080351851
...

correct output
317037701

user output
316586718 29 16384
346736848 29 16384
493852448 29 16384
583056720 30 8192
697399375 30 8192
...

Test 67

Group: 3

Verdict: ACCEPTED

input
3 0

correct output
8

user output
8

Test 68

Group: 3

Verdict:

input
3 1
2

correct output
0

user output
2 2 2
0

Test 69

Group: 3

Verdict:

input
3 1
3

correct output
0

user output
3 2 2
0

Test 70

Group: 3

Verdict:

input
3 2
4
6

correct output
2

user output
4 3 1
6 3 1
2

Test 71

Group: 3

Verdict:

input
3 2
4
7

correct output
2

user output
4 3 1
7 3 1
2

Test 72

Group: 3

Verdict:

input
3 2
5
6

correct output
2

user output
5 3 1
6 3 1
2

Test 73

Group: 3

Verdict:

input
3 2
5
7

correct output
2

user output
5 3 1
7 3 1
2

Test 74

Group: 3

Verdict:

input
3 2
3
6

correct output
0

user output
3 2 2
0

Test 75

Group: 3

Verdict:

input
3 3
4
5
6

correct output
0

user output
4 3 1
5 3 1
6 3 1
0

Test 76

Group: 3

Verdict:

input
3 3
4
6
7

correct output
0

user output
4 3 1
6 3 1
7 3 1
0

Test 77

Group: 3

Verdict:

input
3 4
4
5
6
7

correct output
0

user output
4 3 1
5 3 1
6 3 1
7 3 1
0