CSES - IZhO 2017, day 1 - Results
Submission details
Task:Longest beautiful sequence
Sender:jarvenp
Submission time:2019-02-02 16:47:16 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
Test results
testverdicttimegroup
#1ACCEPTED0.02 s1details
#2ACCEPTED0.02 s1details
#3ACCEPTED0.02 s1details
#4ACCEPTED0.01 s1details
#5ACCEPTED0.02 s1details
#6ACCEPTED0.02 s1details
#7ACCEPTED0.01 s1details
#80.01 s1details
#9ACCEPTED0.03 s1details
#10ACCEPTED0.01 s1details
#11ACCEPTED0.01 s1details
#120.01 s1details
#13ACCEPTED0.02 s1details
#14ACCEPTED0.02 s1details
#15ACCEPTED0.01 s1details
#16ACCEPTED0.02 s1details
#17ACCEPTED0.02 s1details
#18ACCEPTED0.02 s1details
#19ACCEPTED0.02 s1details
#20ACCEPTED0.02 s1details
#21ACCEPTED0.02 s1details
#220.34 s2details
#230.33 s2details
#240.33 s2details
#250.34 s2details
#260.33 s2details
#270.31 s2details
#280.30 s2details
#290.30 s2details
#300.32 s2details
#310.32 s2details
#32ACCEPTED0.30 s2details
#33ACCEPTED0.31 s2details
#34ACCEPTED0.28 s2details
#35ACCEPTED0.30 s2details
#36ACCEPTED0.29 s2details
#37ACCEPTED0.30 s2details
#38ACCEPTED0.30 s2details
#39ACCEPTED0.30 s2details
#40ACCEPTED0.30 s2details
#410.04 s3details
#420.02 s3details
#430.03 s3details
#440.02 s3details
#450.03 s3details
#460.02 s3details
#470.03 s3details
#480.01 s3details
#490.02 s3details
#500.02 s3details
#51ACCEPTED0.01 s3details
#52ACCEPTED0.02 s3details
#53ACCEPTED0.02 s3details
#54ACCEPTED0.03 s3details
#55ACCEPTED0.02 s3details
#560.02 s3details
#570.03 s3details
#580.03 s3details
#590.02 s3details
#600.04 s4details
#610.02 s4details
#620.02 s4details
#630.02 s4details
#640.03 s4details
#650.02 s4details
#660.02 s4details
#670.01 s4details
#680.03 s4details
#690.03 s4details
#700.02 s4details
#710.01 s4details
#720.02 s4details
#730.01 s4details
#740.02 s4details
#750.02 s4details
#760.02 s4details
#770.02 s4details
#780.04 s4details
#790.02 s4details
#800.01 s4details
#810.03 s4details
#820.03 s4details
#830.02 s4details
#840.03 s4details
#850.01 s4details
#860.03 s4details
#870.02 s4details
#880.02 s4details
#890.03 s4details
#900.02 s4details
#910.01 s4details
#920.01 s4details
#930.01 s4details
#940.02 s4details
#950.03 s4details
#960.02 s4details
#970.02 s4details
#980.02 s4details
#990.02 s4details
#1000.02 s4details
#1010.02 s4details
#1020.02 s4details
#1030.02 s4details
#1040.03 s4details
#1050.02 s4details
#1060.02 s4details
#1070.03 s4details
#1080.02 s4details
#1090.02 s4details
#1100.02 s4details
#1110.02 s4details
#1120.03 s4details
#1130.03 s4details

Compiler report

input/code.cpp: In function 'int64_t haku(int64_t, int64_t, int64_t*)':
input/code.cpp:31:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int64_t i=0; i<v[index].size(); i++){
                    ~^~~~~~~~~~~~~~~~

Code

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

int64_t n;
int64_t a[5000];
int64_t k[5000];

vector<int64_t> v[5000];
int64_t done[5000];
int64_t ans2[5000];
bool ok = 0;
int64_t ans =0;

int64_t haku(int64_t index, int64_t d, int64_t p[]){
  if(done[index] != 0){
    return done[index]+d;
  }
  p[d] = index;
  if(v[index].size() == 0){
    if((d+1) > ans){
      for(int64_t i=0; i<d+1; i++){
	ans2[i] = p[i];
      }
      ans = d+1;
    }
    done[index] = 1;
    return d+1;
  }
  int64_t answ = 0;
  for(int64_t i=0; i<v[index].size(); i++){
    answ = max(haku(v[index][i],d+1,p),answ);
  }
  done[index] = answ-d;
  return answ;
}
/*
int64_t haku2(int64_t index, int64_t d){
  ans2[d] = index;
  done[index] = 1;
  if(v[index].size() == 0){
    if(d+1 == ans){
      ok = 1;
    }
    return d+1;
  }
  int64_t answ = 0;
  for(int64_t i=0; i<v[index].size(); i++){
    answ = max(haku2(v[index][i],d+1),answ);
    if(ok){
      return 0;
    }
  }
  return answ;
}
*/
int main(){
  cin >>n;
  for(int64_t i=0; i<n; i++){
    cin >> a[i];
    done[i] = 0;
  }
  for(int64_t i=0; i<n; i++){
    cin >> k[i];
  }
  for(int64_t i=0; i<n-1; i++){
    for(int64_t i2=i+1; i2<n; i2++){
      int64_t b = a[i]&a[i2];
      int64_t s = 0;
      for(int64_t i3=0; i3<21; i3++){
	if((b>>i3)&1){
	  s++;
	}
      }
      if(s == k[i2]){
	v[i].push_back(i2);
      }
    }
  }
  ans = 0;
  int64_t temp[5000];
  for(int64_t i=0; i<n; i++){
    if(!done[i]){
      ans = max(haku(i,0,temp),ans);
    }
  }
  /*
  for(int64_t i=0; i<n; i++){
    done[i] = 0;
  }
  for(int64_t i=0; i<n; i++){
    if(!done[i]){
     haku2(i,0);
    }
    if(ok){
      break;
    }
    }*/
  cout << ans << "\n";
  for(int64_t i=0; i<ans; i++){
    cout << ans2[i]+1 << " ";
  }
  cout << "\n";
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
4
1 2 3 4
10 0 1 0

correct output
4
1 2 3 4

user output
4
1 2 3 4 

Test 2

Group: 1

Verdict: ACCEPTED

input
2
8 9
20 0

correct output
1
1

user output
1

Test 3

Group: 1

Verdict: ACCEPTED

input
5
5 3 5 3 5
10 1 20 1 20

correct output
2
1 2

user output
2
1 2 

Test 4

Group: 1

Verdict: ACCEPTED

input
4
100 100 100 100
20 20 20 20

correct output
1
1

user output
1

Test 5

Group: 1

Verdict: ACCEPTED

input
3
10 10 10
10 0 2

correct output
2
1 3

user output
2
1 3 

Test 6

Group: 1

Verdict: ACCEPTED

input
3
434386 128458 107201
13 18 20

correct output
1
1

user output
1

Test 7

Group: 1

Verdict: ACCEPTED

input
1
700694
17

correct output
1
1

user output
1

Test 8

Group: 1

Verdict:

input
14
216148 356196 874195 349430 22...

correct output
3
2 3 5

user output
3
1 5 1 

Test 9

Group: 1

Verdict: ACCEPTED

input
13
375445 1034546 24018 952919 39...

correct output
2
3 6

user output
2
3 6 

Test 10

Group: 1

Verdict: ACCEPTED

input
13
880258 448181 318223 662719 84...

correct output
3
2 3 12

user output
3
2 3 12 

Test 11

Group: 1

Verdict: ACCEPTED

input
14
93138 744995 814503 642000 681...

correct output
2
4 5

user output
2
4 5 

Test 12

Group: 1

Verdict:

input
15
117241 564565 320855 780748 82...

correct output
3
9 11 15

user output
3
2 15 1 

Test 13

Group: 1

Verdict: ACCEPTED

input
12
574703 442280 619950 936667 66...

correct output
2
2 4

user output
2
1 11 

Test 14

Group: 1

Verdict: ACCEPTED

input
11
714830 1018149 837880 990258 2...

correct output
1
1

user output
1

Test 15

Group: 1

Verdict: ACCEPTED

input
15
685864 299447 708386 531279 15...

correct output
1
1

user output
1

Test 16

Group: 1

Verdict: ACCEPTED

input
15
104263 882956 681936 646213 79...

correct output
1
1

user output
1

Test 17

Group: 1

Verdict: ACCEPTED

input
13
181147 671045 282069 877164 37...

correct output
1
1

user output
1

Test 18

Group: 1

Verdict: ACCEPTED

input
12
1047552 1047040 1046784 104665...

correct output
1
1

user output
1

Test 19

Group: 1

Verdict: ACCEPTED

input
15
1047552 1047040 1046784 104665...

correct output
1
1

user output
1

Test 20

Group: 1

Verdict: ACCEPTED

input
11
1047552 1047040 1046784 104665...

correct output
1
1

user output
1

Test 21

Group: 1

Verdict: ACCEPTED

input
13
1047552 1047040 1046784 104665...

correct output
1
1

user output
1

Test 22

Group: 2

Verdict:

input
4965
139138 110864 458262 1044673 2...

correct output
358
1 4 10 21 22 32 35 69 70 74 87...

user output
358
1 4 10 21 22 32 35 69 70 74 87...

Test 23

Group: 2

Verdict:

input
4924
425955 759278 402527 1035955 5...

correct output
336
1 3 8 43 93 134 150 153 160 16...

user output
336
1 3 8 43 93 110 181 186 189 21...

Test 24

Group: 2

Verdict:

input
4957
869941 822595 396895 94750 206...

correct output
339
15 23 24 45 48 116 118 148 167...

user output
339
1 7 54 68 81 109 174 196 212 2...

Test 25

Group: 2

Verdict:

input
4999
254043 77198 924822 724832 771...

correct output
357
6 17 38 41 52 58 85 92 104 111...

user output
357
1 5 47 50 57 81 83 101 120 123...

Test 26

Group: 2

Verdict:

input
4956
305707 81284 975017 396567 502...

correct output
354
14 16 20 56 94 99 102 108 115 ...

user output
354
1 8 42 65 98 148 188 206 243 2...

Test 27

Group: 2

Verdict:

input
4757
949254 48763 977090 562674 937...

correct output
333
14 16 25 28 34 48 56 63 74 86 ...

user output
333
1 9 50 122 130 165 183 199 226...

Test 28

Group: 2

Verdict:

input
4758
621594 522576 1017588 511192 8...

correct output
314
12 13 14 38 42 45 53 83 116 13...

user output
314
1 16 28 39 45 53 83 116 135 13...

Test 29

Group: 2

Verdict:

input
4810
1003614 738742 873930 234854 8...

correct output
322
7 13 32 43 89 102 106 144 175 ...

user output
322
1 48 64 106 144 169 173 231 26...

Test 30

Group: 2

Verdict:

input
4897
784802 464804 649331 975468 12...

correct output
339
1 3 20 33 40 54 106 120 132 13...

user output
339
1 3 16 31 37 74 88 161 196 207...

Test 31

Group: 2

Verdict:

input
4902
455308 1033824 191820 834424 6...

correct output
351
1 3 15 20 63 81 106 109 112 11...

user output
351
1 3 15 20 63 81 106 109 112 11...

Test 32

Group: 2

Verdict: ACCEPTED

input
4810
534506 764291 358675 603783 33...

correct output
1
1

user output
1

Test 33

Group: 2

Verdict: ACCEPTED

input
4984
984294 316092 719890 642102 79...

correct output
1
1

user output
1

Test 34

Group: 2

Verdict: ACCEPTED

input
4704
893542 291673 670561 92088 724...

correct output
1
1

user output
1

Test 35

Group: 2

Verdict: ACCEPTED

input
4905
358632 32582 955923 774796 935...

correct output
1
1

user output
1

Test 36

Group: 2

Verdict: ACCEPTED

input
4842
689757 407372 644402 158411 83...

correct output
1
1

user output
1

Test 37

Group: 2

Verdict: ACCEPTED

input
4942
1047552 1047040 1046784 104665...

correct output
1
1

user output
1

Test 38

Group: 2

Verdict: ACCEPTED

input
4890
1047552 1047040 1046784 104665...

correct output
1
1

user output
1

Test 39

Group: 2

Verdict: ACCEPTED

input
4907
1047552 1047040 1046784 104665...

correct output
1
1

user output
1

Test 40

Group: 2

Verdict: ACCEPTED

input
4895
1047552 1047040 1046784 104665...

correct output
1
1

user output
1

Test 41

Group: 3

Verdict:

input
99966
81 228 198 77 168 175 7 110 54...

correct output
6296
6 9 19 32 40 41 53 58 64 66 72...

user output
2
2 44 

Test 42

Group: 3

Verdict:

input
99928
220 130 65 177 109 190 250 112...

correct output
6267
2 10 16 18 34 41 54 66 83 105 ...

user output
2
1 34 

Test 43

Group: 3

Verdict:

input
99962
60 47 101 229 144 146 0 145 15...

correct output
6264
1 5 6 25 27 68 83 88 104 122 1...

user output
3
1 94 1 

Test 44

Group: 3

Verdict:

input
99992
165 108 189 99 251 130 233 12 ...

correct output
6384
1 5 14 15 24 25 37 49 50 51 71...

user output
3
6 54 1 

Test 45

Group: 3

Verdict:

input
99913
240 11 76 251 212 122 202 43 7...

correct output
6272
1 6 23 92 105 107 142 148 186 ...

user output
1

Test 46

Group: 3

Verdict:

input
99748
167 91 246 219 199 156 113 225...

correct output
6177
1 13 21 34 44 83 95 120 129 14...

user output
1

Test 47

Group: 3

Verdict:

input
99745
182 195 187 177 124 83 187 93 ...

correct output
6144
1 5 10 26 53 79 82 89 98 107 1...

user output
1

Test 48

Group: 3

Verdict:

input
99986
43 83 250 214 198 183 51 225 1...

correct output
6272
3 15 47 59 69 75 80 111 124 13...

user output
1

Test 49

Group: 3

Verdict:

input
99779
95 238 85 186 199 189 111 121 ...

correct output
6241
9 33 39 89 109 116 131 157 164...

user output
1

Test 50

Group: 3

Verdict:

input
99968
177 249 187 108 119 221 229 21...

correct output
6169
3 14 15 89 100 133 163 173 225...

user output
1

Test 51

Group: 3

Verdict: ACCEPTED

input
99983
58 120 225 108 86 89 106 75 21...

correct output
1
1

user output
1

Test 52

Group: 3

Verdict: ACCEPTED

input
99893
51 101 90 177 106 154 153 240 ...

correct output
1
1

user output
1

Test 53

Group: 3

Verdict: ACCEPTED

input
99912
212 114 166 172 27 57 240 142 ...

correct output
1
1

user output
1

Test 54

Group: 3

Verdict: ACCEPTED

input
99916
78 139 150 166 89 54 102 58 75...

correct output
1
1

user output
1

Test 55

Group: 3

Verdict: ACCEPTED

input
99924
135 154 209 75 184 86 142 71 2...

correct output
1
1

user output
1

Test 56

Group: 3

Verdict:

input
99804
240 232 228 226 225 216 212 21...

correct output
1426
1 71 141 211 281 351 421 491 5...

user output
1

Test 57

Group: 3

Verdict:

input
99847
240 232 228 226 225 216 212 21...

correct output
1427
1 71 141 211 281 351 421 491 5...

user output
1

Test 58

Group: 3

Verdict:

input
99935
240 232 228 226 225 216 212 21...

correct output
1428
1 71 141 211 281 351 421 491 5...

user output
1

Test 59

Group: 3

Verdict:

input
99862
240 232 228 226 225 216 212 21...

correct output
1427
1 71 141 211 281 351 421 491 5...

user output
1

Test 60

Group: 4

Verdict:

input
99913
325786 525502 147022 721216 30...

correct output
7034
17 26 28 29 32 39 40 53 59 72 ...

user output
(empty)

Test 61

Group: 4

Verdict:

input
99910
1024182 482807 317440 686659 6...

correct output
7045
2 8 15 36 62 70 79 95 134 140 ...

user output
(empty)

Test 62

Group: 4

Verdict:

input
99977
489800 986390 1023956 116005 3...

correct output
7147
2 3 20 21 28 56 74 76 91 93 10...

user output
(empty)

Test 63

Group: 4

Verdict:

input
99944
4684 252923 460835 1046608 194...

correct output
7038
9 21 27 42 71 80 116 135 166 1...

user output
(empty)

Test 64

Group: 4

Verdict:

input
99909
161106 985609 251308 821078 10...

correct output
7169
7 10 12 14 30 37 49 64 112 122...

user output
(empty)

Test 65

Group: 4

Verdict:

input
99759
997654 1019744 588918 778457 7...

correct output
6735
6 16 24 36 48 83 110 111 119 1...

user output
(empty)

Test 66

Group: 4

Verdict:

input
99852
710202 630188 805435 1024711 7...

correct output
6713
1 3 4 25 45 92 111 114 123 137...

user output
(empty)

Test 67

Group: 4

Verdict:

input
99703
92663 875059 977010 763181 475...

correct output
6748
8 11 17 25 42 69 72 82 95 97 9...

user output
(empty)

Test 68

Group: 4

Verdict:

input
99749
364331 15709 396687 838045 821...

correct output
6607
2 18 43 61 88 101 115 122 163 ...

user output
(empty)

Test 69

Group: 4

Verdict:

input
99778
813471 678671 851107 869366 77...

correct output
6722
2 5 12 38 77 113 122 152 156 1...

user output
(empty)

Test 70

Group: 4

Verdict:

input
99766
649379 864427 504969 304046 54...

correct output
1
1

user output
(empty)

Test 71

Group: 4

Verdict:

input
99749
357157 483542 820714 852717 35...

correct output
1
1

user output
(empty)

Test 72

Group: 4

Verdict:

input
99811
1001868 902316 372815 995859 6...

correct output
1
1

user output
(empty)

Test 73

Group: 4

Verdict:

input
99853
94962 538203 579339 787949 834...

correct output
1
1

user output
(empty)

Test 74

Group: 4

Verdict:

input
99732
208647 757980 403911 927208 94...

correct output
1
1

user output
(empty)

Test 75

Group: 4

Verdict:

input
100000
1047552 1047040 1046784 104665...

correct output
1
1

user output
(empty)

Test 76

Group: 4

Verdict:

input
99981
1047552 1047040 1046784 104665...

correct output
1
1

user output
(empty)

Test 77

Group: 4

Verdict:

input
99714
1047552 1047040 1046784 104665...

correct output
1
1

user output
(empty)

Test 78

Group: 4

Verdict:

input
99944
1047552 1047040 1046784 104665...

correct output
1
1

user output
(empty)

Test 79

Group: 4

Verdict:

input
100000
983040 950272 933888 925696 92...

correct output
21
1 4846 9691 14536 19381 24226 ...

user output
(empty)

Test 80

Group: 4

Verdict:

input
100000
1015808 999424 991232 987136 9...

correct output
7
1 15505 31009 46513 62017 7752...

user output
(empty)

Test 81

Group: 4

Verdict:

input
100000
1032192 1024000 1019904 101785...

correct output
3
1 38761 77521

user output
(empty)

Test 82

Group: 4

Verdict:

input
100000
1040384 1036288 1034240 103321...

correct output
2
1 77521

user output
(empty)

Test 83

Group: 4

Verdict:

input
100000
1044480 1042432 1041408 104089...

correct output
1
1

user output
(empty)

Test 84

Group: 4

Verdict:

input
100000
1046528 1045504 1044992 104473...

correct output
1
1

user output
(empty)

Test 85

Group: 4

Verdict:

input
100000
1047552 1047040 1046784 104665...

correct output
1
1

user output
(empty)

Test 86

Group: 4

Verdict:

input
100000
983040 950272 933888 925696 92...

correct output
11
1 14536 18001 33917 36002 5329...

user output
(empty)

Test 87

Group: 4

Verdict:

input
100000
1015808 999424 991232 987136 9...

correct output
11
1 15505 18001 31010 36002 4651...

user output
(empty)

Test 88

Group: 4

Verdict:

input
100000
1032192 1024000 1019904 101785...

correct output
6
17985 18001 38763 54003 77525 ...

user output
(empty)

Test 89

Group: 4

Verdict:

input
100000
1040384 1036288 1034240 103321...

correct output
4
17883 18001 77525 90005

user output
(empty)

Test 90

Group: 4

Verdict:

input
100000
1044480 1042432 1041408 104089...

correct output
2
17851 18001

user output
(empty)

Test 91

Group: 4

Verdict:

input
100000
1046528 1045504 1044992 104473...

correct output
2
17997 18001

user output
(empty)

Test 92

Group: 4

Verdict:

input
100000
1047552 1047040 1046784 104665...

correct output
2
17943 18001

user output
(empty)

Test 93

Group: 4

Verdict:

input
100000
308786 408594 130568 815433 28...

correct output
7211
5 6 13 29 31 34 37 41 42 48 63...

user output
(empty)

Test 94

Group: 4

Verdict:

input
100000
447299 571486 502296 63681 801...

correct output
7032
6 16 30 32 34 68 93 123 164 19...

user output
(empty)

Test 95

Group: 4

Verdict:

input
100000
289362 974697 152279 614575 32...

correct output
7092
5 9 13 23 33 41 46 86 88 99 12...

user output
(empty)

Test 96

Group: 4

Verdict:

input
100000
13379 1017022 1008749 179475 1...

correct output
14167
3 4 7 15 23 24 26 39 43 56 58 ...

user output
(empty)

Test 97

Group: 4

Verdict:

input
100000
517839 718867 811739 616345 25...

correct output
14159
1 7 32 33 43 53 58 64 68 72 10...

user output
(empty)

Test 98

Group: 4

Verdict:

input
100000
429436 319690 717606 609681 28...

correct output
14125
2 7 13 21 36 45 47 52 54 69 78...

user output
(empty)

Test 99

Group: 4

Verdict:

input
100000
540824 80929 664264 971202 507...

correct output
14121
1 3 8 15 24 28 29 30 34 35 45 ...

user output
(empty)

Test 100

Group: 4

Verdict:

input
100000
502131 215498 829032 46710 418...

correct output
14010
2 3 4 7 9 27 31 33 44 49 54 55...

user output
(empty)

Test 101

Group: 4

Verdict:

input
100000
148194 140924 164801 605018 68...

correct output
13976
2 5 14 28 30 32 44 49 50 54 68...

user output
(empty)

Test 102

Group: 4

Verdict:

input
100000
1047552 1047040 1046784 104665...

correct output
3
25869 82151 91360

user output
(empty)

Test 103

Group: 4

Verdict:

input
100000
1046528 1045504 1044992 104473...

correct output
2
94744 98281

user output
(empty)

Test 104

Group: 4

Verdict:

input
100000
1044480 1042432 1041408 104089...

correct output
3
43916 76791 81820

user output
(empty)

Test 105

Group: 4

Verdict:

input
100000
1048064 1047808 1047680 104761...

correct output
2
57817 68721

user output
(empty)

Test 106

Group: 4

Verdict:

input
100000
1048320 1048192 1048128 104809...

correct output
3
36249 37226 91703

user output
(empty)

Test 107

Group: 4

Verdict:

input
100000
1048448 1048384 1048352 104833...

correct output
4
7288 9900 50462 87420

user output
(empty)

Test 108

Group: 4

Verdict:

input
100000
1048512 1048480 1048464 104845...

correct output
5
6467 20650 45227 67776 83987

user output
(empty)

Test 109

Group: 4

Verdict:

input
100000
1048544 1048528 1048520 104851...

correct output
8
15422 30926 46430 61934 77438 ...

user output
(empty)

Test 110

Group: 4

Verdict:

input
100000
1048560 1048552 1048548 104854...

correct output
22
3108 7953 12798 17643 22488 27...

user output
(empty)

Test 111

Group: 4

Verdict:

input
100000
154346 609565 1022517 1033712 ...

correct output
6760
6 20 25 38 40 50 64 66 88 92 1...

user output
(empty)

Test 112

Group: 4

Verdict:

input
100000
741070 212083 251667 382904 67...

correct output
6788
11 15 37 54 60 83 97 104 120 1...

user output
(empty)

Test 113

Group: 4

Verdict:

input
100000
969933 305838 682108 643499 51...

correct output
6632
4 26 28 59 65 78 114 119 124 1...

user output
(empty)