— Dark mode

Datatähti 2019 loppu

Binääripuu

  • Start: 2019-01-17 12:00:00
  • End: 2019-01-17 17:00:00
Submission details
Task:Binääripuu
Sender:Roope Salmi
Submission time:2019-01-17 12:57:24 +0200
Language:C++
Status:READY
Result:26
Feedback
subtaskverdictscore
#10
#2ACCEPTED26
#30
Test results
testverdicttimesubtask
#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

Subtask: 1

Verdict:

input
4 3
10
5
13
view save

correct output
12
view save

user output
5 3 2
13 4 1
12
view save

Test 2

Subtask: 1

Verdict: ACCEPTED

input
2 0
view save

correct output
2
view save

user output
2
view save

Test 3

Subtask: 1

Verdict:

input
2 1
2
view save

correct output
0
view save

user output
2 2 1
0
view save

Test 4

Subtask: 1

Verdict:

input
2 1
3
view save

correct output
0
view save

user output
3 2 1
0
view save

Test 5

Subtask: 1

Verdict:

input
2 2
2
3
view save

correct output
0
view save

user output
2 2 1
3 2 1
0
view save

Test 6

Subtask: 1

Verdict: ACCEPTED

input
6 0
view save

correct output
512
view save

user output
512
view save

Test 7

Subtask: 1

Verdict:

input
6 1
29
view save

correct output
448
view save

user output
29 5 2
448
view save

Test 8

Subtask: 1

Verdict:

input
6 1
63
view save

correct output
480
view save

user output
63 6 1
480
view save

Test 9

Subtask: 1

Verdict:

input
6 10
50
63
56
5
...
view save

correct output
132
view save

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

Test 10

Subtask: 1

Verdict:

input
6 10
25
57
62
42
...
view save

correct output
162
view save

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

Test 11

Subtask: 1

Verdict:

input
6 10
14
26
34
42
...
view save

correct output
126
view save

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

Test 12

Subtask: 1

Verdict:

input
6 10
21
60
23
59
...
view save

correct output
128
view save

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

Test 13

Subtask: 1

Verdict:

input
6 10
8
30
32
16
...
view save

correct output
0
view save

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

Test 14

Subtask: 1

Verdict:

input
6 20
46
39
55
24
...
view save

correct output
48
view save

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

Test 15

Subtask: 1

Verdict:

input
6 25
36
23
27
33
...
view save

correct output
4
view save

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

Test 16

Subtask: 1

Verdict:

input
6 62
42
11
4
61
...
view save

correct output
0
view save

user output
2 2 16
3 2 16
0
view save

Test 17

Subtask: 1

Verdict:

input
6 32
62
38
57
35
...
view save

correct output
0
view save

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

Test 18

Subtask: 1

Verdict:

input
6 21
38
51
47
35
...
view save

correct output
60
view save

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

Test 19

Subtask: 1

Verdict:

input
6 31
59
15
3
26
...
view save

correct output
0
view save

user output
3 2 16
0
view save

Test 20

Subtask: 1

Verdict:

input
6 14
13
53
55
26
...
view save

correct output
256
view save

user output
6 3 8
256
view save

Test 21

Subtask: 1

Verdict:

input
5 10
5
17
21
7
...
view save

correct output
6
view save

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

Test 22

Subtask: 1

Verdict:

input
6 5
38
18
31
44
...
view save

correct output
312
view save

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

Test 23

Subtask: 1

Verdict: ACCEPTED

input
3 0
view save

correct output
8
view save

user output
8
view save

Test 24

Subtask: 1

Verdict:

input
3 1
2
view save

correct output
0
view save

user output
2 2 2
0
view save

Test 25

Subtask: 1

Verdict:

input
3 1
3
view save

correct output
0
view save

user output
3 2 2
0
view save

Test 26

Subtask: 1

Verdict:

input
3 2
4
6
view save

correct output
2
view save

user output
4 3 1
6 3 1
2
view save

Test 27

Subtask: 1

Verdict:

input
3 2
4
7
view save

correct output
2
view save

user output
4 3 1
7 3 1
2
view save

Test 28

Subtask: 1

Verdict:

input
3 2
5
6
view save

correct output
2
view save

user output
5 3 1
6 3 1
2
view save

Test 29

Subtask: 1

Verdict:

input
3 2
5
7
view save

correct output
2
view save

user output
5 3 1
7 3 1
2
view save

Test 30

Subtask: 1

Verdict:

input
3 2
3
6
view save

correct output
0
view save

user output
3 2 2
0
view save

Test 31

Subtask: 1

Verdict:

input
3 3
4
5
6
view save

correct output
0
view save

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

Test 32

Subtask: 1

Verdict:

input
3 3
4
6
7
view save

correct output
0
view save

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

Test 33

Subtask: 1

Verdict:

input
3 4
4
5
6
7
view save

correct output
0
view save

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

Test 34

Subtask: 1

Verdict: ACCEPTED

input
5 0
view save

correct output
128
view save

user output
128
view save

Test 35

Subtask: 1

Verdict:

input
5 1
14
view save

correct output
96
view save

user output
14 4 2
96
view save

Test 36

Subtask: 2

Verdict: ACCEPTED

input
2 0
view save

correct output
2
view save

user output
2
view save

Test 37

Subtask: 2

Verdict: ACCEPTED

input
3 0
view save

correct output
8
view save

user output
8
view save

Test 38

Subtask: 2

Verdict: ACCEPTED

input
4 0
view save

correct output
32
view save

user output
32
view save

Test 39

Subtask: 2

Verdict: ACCEPTED

input
23 0
view save

correct output
92960636
view save

user output
92960636
view save

Test 40

Subtask: 2

Verdict: ACCEPTED

input
36 0
view save

correct output
635008130
view save

user output
635008130
view save

Test 41

Subtask: 2

Verdict: ACCEPTED

input
42 0
view save

correct output
993282280
view save

user output
993282280
view save

Test 42

Subtask: 2

Verdict: ACCEPTED

input
57 0
view save

correct output
608377687
view save

user output
608377687
view save

Test 43

Subtask: 2

Verdict: ACCEPTED

input
58 0
view save

correct output
433510734
view save

user output
433510734
view save

Test 44

Subtask: 2

Verdict: ACCEPTED

input
59 0
view save

correct output
734042929
view save

user output
734042929
view save

Test 45

Subtask: 2

Verdict: ACCEPTED

input
60 0
view save

correct output
936171702
view save

user output
936171702
view save

Test 46

Subtask: 3

Verdict: ACCEPTED

input
2 0
view save

correct output
2
view save

user output
2
view save

Test 47

Subtask: 3

Verdict:

input
2 1
2
view save

correct output
0
view save

user output
2 2 1
0
view save

Test 48

Subtask: 3

Verdict:

input
2 1
3
view save

correct output
0
view save

user output
3 2 1
0
view save

Test 49

Subtask: 3

Verdict:

input
2 2
2
3
view save

correct output
0
view save

user output
2 2 1
3 2 1
0
view save

Test 50

Subtask: 3

Verdict: ACCEPTED

input
59 0
view save

correct output
734042929
view save

user output
734042929
view save

Test 51

Subtask: 3

Verdict: ACCEPTED

input
60 0
view save

correct output
936171702
view save

user output
936171702
view save

Test 52

Subtask: 3

Verdict:

input
60 1
2
view save

correct output
0
view save

user output
2 2 288230376151711744
0
view save

Test 53

Subtask: 3

Verdict:

input
60 1
576460752303423487
view save

correct output
399775198
view save

user output
576460752303423487 59 2
399775198
view save

Test 54

Subtask: 3

Verdict:

input
60 1
1152921504606846975
view save

correct output
667973450
view save

user output
1152921504606846975 60 1
667973450
view save

Test 55

Subtask: 3

Verdict:

input
60 100000
793144025126277478
493960657696318193
320344157019848454
997683950258055349
...
view save

correct output
12813436
view save

user output
10627238995021 44 65536
18016018239554 45 32768
20840493737371 45 32768
37616681635432 46 

...
Truncated

Test 56

Subtask: 3

Verdict:

input
60 100000
986789393060040220
494066507202684187
290830182157570659
210871095549437400
...
view save

correct output
95910570
view save

user output
16034183462491 44 65536
57893425701277 46 16384
63631897254626 46 16384
90577439530378 47 

...
Truncated

Test 57

Subtask: 3

Verdict:

input
60 100000
562299894758506682
731132428235172865
481500339045425690
208947005967360560
...
view save

correct output
331624281
view save

user output
7014821912901 43 131072
10977096920815 44 65536
11790851036703 44 65536
16313806427959 44 

...
Truncated

Test 58

Subtask: 3

Verdict:

input
60 100000
257846911019866261
803021202233459674
658685893766403373
874237705485665885
...
view save

correct output
880725152
view save

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

...
Truncated

Test 59

Subtask: 3

Verdict:

input
60 100000
681388061028265547
990382999862855868
290694941402209648
491574111397234946
...
view save

correct output
768320742
view save

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

...
Truncated

Test 60

Subtask: 3

Verdict:

input
60 100000
816968727394104576
879176301780517486
1075817811951859004
632046213104404023
...
view save

correct output
111155168
view save

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

...
Truncated

Test 61

Subtask: 3

Verdict:

input
60 100000
406817930303406656
101704482575856800
406817930303412346
813635860606874021
...
view save

correct output
295651662
view save

user output
12415097970685 44 65536
295651662
view save

Test 62

Subtask: 3

Verdict:

input
59 100000
234885934259928845
244746379456935555
40048493361902167
530369614866009610
...
view save

correct output
78892926
view save

user output
6051393097757 43 65536
25282689674435 45 16384
28263077276156 45 16384
33595045590121 45 1

...
Truncated

Test 63

Subtask: 3

Verdict:

input
16 65534
26355
15205
3420
22822
...
view save

correct output
0
view save

user output
2 2 16384
3 2 16384
0
view save

Test 64

Subtask: 3

Verdict:

input
60 99999
1030879879260090869
925369330408563145
403438777989811739
321883235203598800
...
view save

correct output
596899803
view save

user output
2379051592350 42 262144
5967373309128 43 131072
8114697003106 43 131072
29112527788213 45 

...
Truncated

Test 65

Subtask: 3

Verdict:

input
60 100000
418885324976523921
418885324976523063
837770649953084829
104721331244134167
...
view save

correct output
0
view save

user output
2 2 288230376151711744
0
view save

Test 66

Subtask: 3

Verdict:

input
43 100000
5497882741157
4163319796881
3705445016042
8647080351851
...
view save

correct output
317037701
view save

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

Test 67

Subtask: 3

Verdict: ACCEPTED

input
3 0
view save

correct output
8
view save

user output
8
view save

Test 68

Subtask: 3

Verdict:

input
3 1
2
view save

correct output
0
view save

user output
2 2 2
0
view save

Test 69

Subtask: 3

Verdict:

input
3 1
3
view save

correct output
0
view save

user output
3 2 2
0
view save

Test 70

Subtask: 3

Verdict:

input
3 2
4
6
view save

correct output
2
view save

user output
4 3 1
6 3 1
2
view save

Test 71

Subtask: 3

Verdict:

input
3 2
4
7
view save

correct output
2
view save

user output
4 3 1
7 3 1
2
view save

Test 72

Subtask: 3

Verdict:

input
3 2
5
6
view save

correct output
2
view save

user output
5 3 1
6 3 1
2
view save

Test 73

Subtask: 3

Verdict:

input
3 2
5
7
view save

correct output
2
view save

user output
5 3 1
7 3 1
2
view save

Test 74

Subtask: 3

Verdict:

input
3 2
3
6
view save

correct output
0
view save

user output
3 2 2
0
view save

Test 75

Subtask: 3

Verdict:

input
3 3
4
5
6
view save

correct output
0
view save

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

Test 76

Subtask: 3

Verdict:

input
3 3
4
6
7
view save

correct output
0
view save

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

Test 77

Subtask: 3

Verdict:

input
3 4
4
5
6
7
view save

correct output
0
view save

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

Tasks

A Summa-B Bittijono-C Auringonlasku-D Binääripuu-E Funktio-F Robotti-G Luokittelija-

Submissions (Roope Salmi)

2019-01-17 12:58:59 1002019-01-17 12:57:24 26