oj.uz

Submission #36928

# Submission time Handle Problem Language Result Execution time Memory
36928 2017-12-18T17:32:15 Z top34051 Longest beautiful sequence (IZhO17_subsequence) C++14
100 / 100
 5229 ms 48780 KB 
#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second

const int maxn = 1e5 + 5;
const int cut = 1024;

int n;
int p[maxn], k[maxn];
int cnt[cut];
int dp[maxn], rec[cut][cut][11];
int track[maxn];
vector<int> res;

int main() {
    int i,x,y,a,b;
    pii ans;
    scanf("%d",&n);
    for(i=1;i<=n;++i) scanf("%d",&p[i]);
    for(i=1;i<=n;++i) scanf("%d",&k[i]);
    for(x=0;x<cut;++x) cnt[x] = __builtin_popcount(x);
    ans = {0,0};
    for(i=1;i<=n;++i) {
        a = p[i]>>10; b = p[i]%cut; dp[i] = 1;
        //fix C (x)
        for(x=0;x<cut;++x) {
            int want = k[i] - cnt[a&x];
            if(want<0 || want>10) continue;
            int pos = rec[x][b][want];
            if(dp[i] < dp[pos] + 1) dp[i] = dp[pos] + 1, track[i] = pos;
        }
        if(ans.X < dp[i]) ans = make_pair(dp[i], i);
        //fix B (x)
        for(x=0;x<cut;++x) {
            int want = cnt[b&x];
            int pos = rec[a][x][want];
            if(dp[pos] < dp[i]) rec[a][x][want] = i;
        }
    }
    printf("%d\n",ans.X);
    x = ans.Y;
    while(x) res.emplace_back(x), x = track[x];
    reverse(res.begin(), res.end());
    for(auto t : res) printf("%d ",t);
}

Compilation message

subsequence.cpp: In function 'int main()':
subsequence.cpp:19:13: warning: unused variable 'y' [-Wunused-variable]
     int i,x,y,a,b;
             ^
subsequence.cpp:21:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
subsequence.cpp:22:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;++i) scanf("%d",&p[i]);
                                        ^
subsequence.cpp:23:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;++i) scanf("%d",&k[i]);
                                        ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 48636 KB answer = 4
2 Correct 0 ms 48636 KB answer = 1
3 Correct 0 ms 48636 KB answer = 2
4 Correct 0 ms 48636 KB answer = 1
5 Correct 0 ms 48636 KB answer = 2
6 Correct 0 ms 48636 KB answer = 1
7 Correct 0 ms 48636 KB answer = 1
8 Correct 3 ms 48636 KB answer = 3
9 Correct 3 ms 48636 KB answer = 2
10 Correct 3 ms 48636 KB answer = 3
11 Correct 0 ms 48636 KB answer = 2
12 Correct 0 ms 48636 KB answer = 3
13 Correct 3 ms 48636 KB answer = 2
14 Correct 0 ms 48636 KB answer = 1
15 Correct 3 ms 48636 KB answer = 1
16 Correct 3 ms 48636 KB answer = 1
17 Correct 3 ms 48636 KB answer = 1
18 Correct 0 ms 48636 KB answer = 1
19 Correct 3 ms 48636 KB answer = 1
20 Correct 3 ms 48636 KB answer = 1
21 Correct 3 ms 48636 KB answer = 1

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 48636 KB answer = 4
2 Correct 0 ms 48636 KB answer = 1
3 Correct 0 ms 48636 KB answer = 2
4 Correct 0 ms 48636 KB answer = 1
5 Correct 0 ms 48636 KB answer = 2
6 Correct 0 ms 48636 KB answer = 1
7 Correct 0 ms 48636 KB answer = 1
8 Correct 3 ms 48636 KB answer = 3
9 Correct 3 ms 48636 KB answer = 2
10 Correct 3 ms 48636 KB answer = 3
11 Correct 0 ms 48636 KB answer = 2
12 Correct 0 ms 48636 KB answer = 3
13 Correct 3 ms 48636 KB answer = 2
14 Correct 0 ms 48636 KB answer = 1
15 Correct 3 ms 48636 KB answer = 1
16 Correct 3 ms 48636 KB answer = 1
17 Correct 3 ms 48636 KB answer = 1
18 Correct 0 ms 48636 KB answer = 1
19 Correct 3 ms 48636 KB answer = 1
20 Correct 3 ms 48636 KB answer = 1
21 Correct 3 ms 48636 KB answer = 1
22 Correct 153 ms 48636 KB answer = 358
23 Correct 146 ms 48636 KB answer = 336
24 Correct 159 ms 48636 KB answer = 339
25 Correct 163 ms 48636 KB answer = 357
26 Correct 126 ms 48636 KB answer = 354
27 Correct 136 ms 48636 KB answer = 333
28 Correct 143 ms 48636 KB answer = 314
29 Correct 106 ms 48636 KB answer = 322
30 Correct 116 ms 48636 KB answer = 339
31 Correct 136 ms 48636 KB answer = 351
32 Correct 219 ms 48636 KB answer = 1
33 Correct 203 ms 48636 KB answer = 1
34 Correct 199 ms 48636 KB answer = 1
35 Correct 193 ms 48636 KB answer = 1
36 Correct 196 ms 48636 KB answer = 1
37 Correct 43 ms 48636 KB answer = 1
38 Correct 39 ms 48636 KB answer = 1
39 Correct 46 ms 48636 KB answer = 1
40 Correct 43 ms 48636 KB answer = 1

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 48636 KB answer = 4
2 Correct 0 ms 48636 KB answer = 1
3 Correct 0 ms 48636 KB answer = 2
4 Correct 0 ms 48636 KB answer = 1
5 Correct 0 ms 48636 KB answer = 2
6 Correct 0 ms 48636 KB answer = 1
7 Correct 0 ms 48636 KB answer = 1
8 Correct 3 ms 48636 KB answer = 3
9 Correct 3 ms 48636 KB answer = 2
10 Correct 3 ms 48636 KB answer = 3
11 Correct 0 ms 48636 KB answer = 2
12 Correct 0 ms 48636 KB answer = 3
13 Correct 3 ms 48636 KB answer = 2
14 Correct 0 ms 48636 KB answer = 1
15 Correct 3 ms 48636 KB answer = 1
16 Correct 3 ms 48636 KB answer = 1
17 Correct 3 ms 48636 KB answer = 1
18 Correct 0 ms 48636 KB answer = 1
19 Correct 3 ms 48636 KB answer = 1
20 Correct 3 ms 48636 KB answer = 1
21 Correct 3 ms 48636 KB answer = 1
22 Correct 153 ms 48636 KB answer = 358
23 Correct 146 ms 48636 KB answer = 336
24 Correct 159 ms 48636 KB answer = 339
25 Correct 163 ms 48636 KB answer = 357
26 Correct 126 ms 48636 KB answer = 354
27 Correct 136 ms 48636 KB answer = 333
28 Correct 143 ms 48636 KB answer = 314
29 Correct 106 ms 48636 KB answer = 322
30 Correct 116 ms 48636 KB answer = 339
31 Correct 136 ms 48636 KB answer = 351
32 Correct 219 ms 48636 KB answer = 1
33 Correct 203 ms 48636 KB answer = 1
34 Correct 199 ms 48636 KB answer = 1
35 Correct 193 ms 48636 KB answer = 1
36 Correct 196 ms 48636 KB answer = 1
37 Correct 43 ms 48636 KB answer = 1
38 Correct 39 ms 48636 KB answer = 1
39 Correct 46 ms 48636 KB answer = 1
40 Correct 43 ms 48636 KB answer = 1
41 Correct 729 ms 48780 KB answer = 6296
42 Correct 769 ms 48780 KB answer = 6267
43 Correct 753 ms 48780 KB answer = 6264
44 Correct 753 ms 48780 KB answer = 6384
45 Correct 753 ms 48780 KB answer = 6272
46 Correct 679 ms 48780 KB answer = 6177
47 Correct 669 ms 48780 KB answer = 6144
48 Correct 709 ms 48780 KB answer = 6272
49 Correct 719 ms 48780 KB answer = 6241
50 Correct 733 ms 48780 KB answer = 6169
51 Correct 443 ms 48636 KB answer = 1
52 Correct 439 ms 48636 KB answer = 1
53 Correct 416 ms 48636 KB answer = 1
54 Correct 466 ms 48636 KB answer = 1
55 Correct 423 ms 48636 KB answer = 1
56 Correct 789 ms 48636 KB answer = 1426
57 Correct 799 ms 48636 KB answer = 1427
58 Correct 833 ms 48636 KB answer = 1428
59 Correct 806 ms 48636 KB answer = 1427

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 48636 KB answer = 4
2 Correct 0 ms 48636 KB answer = 1
3 Correct 0 ms 48636 KB answer = 2
4 Correct 0 ms 48636 KB answer = 1
5 Correct 0 ms 48636 KB answer = 2
6 Correct 0 ms 48636 KB answer = 1
7 Correct 0 ms 48636 KB answer = 1
8 Correct 3 ms 48636 KB answer = 3
9 Correct 3 ms 48636 KB answer = 2
10 Correct 3 ms 48636 KB answer = 3
11 Correct 0 ms 48636 KB answer = 2
12 Correct 0 ms 48636 KB answer = 3
13 Correct 3 ms 48636 KB answer = 2
14 Correct 0 ms 48636 KB answer = 1
15 Correct 3 ms 48636 KB answer = 1
16 Correct 3 ms 48636 KB answer = 1
17 Correct 3 ms 48636 KB answer = 1
18 Correct 0 ms 48636 KB answer = 1
19 Correct 3 ms 48636 KB answer = 1
20 Correct 3 ms 48636 KB answer = 1
21 Correct 3 ms 48636 KB answer = 1
22 Correct 153 ms 48636 KB answer = 358
23 Correct 146 ms 48636 KB answer = 336
24 Correct 159 ms 48636 KB answer = 339
25 Correct 163 ms 48636 KB answer = 357
26 Correct 126 ms 48636 KB answer = 354
27 Correct 136 ms 48636 KB answer = 333
28 Correct 143 ms 48636 KB answer = 314
29 Correct 106 ms 48636 KB answer = 322
30 Correct 116 ms 48636 KB answer = 339
31 Correct 136 ms 48636 KB answer = 351
32 Correct 219 ms 48636 KB answer = 1
33 Correct 203 ms 48636 KB answer = 1
34 Correct 199 ms 48636 KB answer = 1
35 Correct 193 ms 48636 KB answer = 1
36 Correct 196 ms 48636 KB answer = 1
37 Correct 43 ms 48636 KB answer = 1
38 Correct 39 ms 48636 KB answer = 1
39 Correct 46 ms 48636 KB answer = 1
40 Correct 43 ms 48636 KB answer = 1
41 Correct 729 ms 48780 KB answer = 6296
42 Correct 769 ms 48780 KB answer = 6267
43 Correct 753 ms 48780 KB answer = 6264
44 Correct 753 ms 48780 KB answer = 6384
45 Correct 753 ms 48780 KB answer = 6272
46 Correct 679 ms 48780 KB answer = 6177
47 Correct 669 ms 48780 KB answer = 6144
48 Correct 709 ms 48780 KB answer = 6272
49 Correct 719 ms 48780 KB answer = 6241
50 Correct 733 ms 48780 KB answer = 6169
51 Correct 443 ms 48636 KB answer = 1
52 Correct 439 ms 48636 KB answer = 1
53 Correct 416 ms 48636 KB answer = 1
54 Correct 466 ms 48636 KB answer = 1
55 Correct 423 ms 48636 KB answer = 1
56 Correct 789 ms 48636 KB answer = 1426
57 Correct 799 ms 48636 KB answer = 1427
58 Correct 833 ms 48636 KB answer = 1428
59 Correct 806 ms 48636 KB answer = 1427
60 Correct 3176 ms 48780 KB answer = 7034
61 Correct 3363 ms 48780 KB answer = 7045
62 Correct 3329 ms 48780 KB answer = 7147
63 Correct 3159 ms 48780 KB answer = 7038
64 Correct 3269 ms 48780 KB answer = 7169
65 Correct 3163 ms 48780 KB answer = 6735
66 Correct 3016 ms 48780 KB answer = 6713
67 Correct 3313 ms 48780 KB answer = 6748
68 Correct 3269 ms 48780 KB answer = 6607
69 Correct 3239 ms 48780 KB answer = 6722
70 Correct 5126 ms 48636 KB answer = 1
71 Correct 5229 ms 48636 KB answer = 1
72 Correct 4869 ms 48636 KB answer = 1
73 Correct 4499 ms 48636 KB answer = 1
74 Correct 4596 ms 48636 KB answer = 1
75 Correct 1613 ms 48636 KB answer = 1
76 Correct 1663 ms 48636 KB answer = 1
77 Correct 1646 ms 48636 KB answer = 1
78 Correct 1586 ms 48636 KB answer = 1
79 Correct 1903 ms 48636 KB answer = 21
80 Correct 2419 ms 48636 KB answer = 7
81 Correct 2729 ms 48636 KB answer = 3
82 Correct 2496 ms 48636 KB answer = 2
83 Correct 2116 ms 48636 KB answer = 1
84 Correct 1749 ms 48636 KB answer = 1
85 Correct 1439 ms 48636 KB answer = 1
86 Correct 1656 ms 48636 KB answer = 11
87 Correct 2449 ms 48636 KB answer = 11
88 Correct 2876 ms 48636 KB answer = 6
89 Correct 2586 ms 48636 KB answer = 4
90 Correct 2069 ms 48636 KB answer = 2
91 Correct 1813 ms 48636 KB answer = 2
92 Correct 1503 ms 48636 KB answer = 2
93 Correct 3256 ms 48780 KB answer = 7211
94 Correct 3279 ms 48780 KB answer = 7032
95 Correct 3366 ms 48780 KB answer = 7092
96 Correct 4219 ms 48780 KB answer = 14167
97 Correct 4369 ms 48780 KB answer = 14159
98 Correct 4163 ms 48780 KB answer = 14125
99 Correct 4229 ms 48780 KB answer = 14121
100 Correct 4249 ms 48780 KB answer = 14010
101 Correct 4173 ms 48780 KB answer = 13976
102 Correct 1389 ms 48636 KB answer = 3
103 Correct 1673 ms 48636 KB answer = 2
104 Correct 1999 ms 48636 KB answer = 3
105 Correct 1479 ms 48636 KB answer = 2
106 Correct 1513 ms 48636 KB answer = 3
107 Correct 1753 ms 48636 KB answer = 4
108 Correct 1623 ms 48636 KB answer = 5
109 Correct 1283 ms 48636 KB answer = 8
110 Correct 873 ms 48636 KB answer = 22
111 Correct 3173 ms 48780 KB answer = 6760
112 Correct 3239 ms 48780 KB answer = 6788
113 Correct 3196 ms 48780 KB answer = 6632