oj.uz

Submission #532344

# Submission time Handle Problem Language Result Execution time Memory
532344 2022-03-02T17:59:34 Z SansPapyrus683 Longest beautiful sequence (IZhO17_subsequence) C++17
40 / 100
 6000 ms 4148 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <bit>
#include <map>
 
using std::cout;
using std::endl;
using std::vector;
using std::pair;
 
/**
 * https://oj.uz/problem/view/IZhO17_subsequence
 * 5
 * 5 3 5 3 5
 * 10 1 20 1 20 should output
 * 2
 * 1 2
 */
int main() {
    int size;
    std::cin >> size;
    vector<int> arr(size);
    for (int& i : arr) {
        std::cin >> i;
    }
    vector<int> targets(size);
    for (int& t : targets) {
        std::cin >> t;
    }
  
    std::map<int, pair<int, int>> got_seqs{{arr[0], {1, 0}}};
    vector<int> prev(size);
    int longest = 1;
    int longest_end = 0;
    for (int i = 1; i < size; i++) {
        int n = arr[i];
        int this_max = 1;
        prev[i] = i;
        for (const auto& [p, p_info] : got_seqs) {
            if (std::__popcount(n & p) == targets[i]) {
                if (p_info.first + 1 > this_max) {
                    this_max = p_info.first + 1;
                    prev[i] = p_info.second;
                }
            }
        }
        if (this_max > got_seqs[n].first) {
            got_seqs[n] = {this_max, i};
        }
        if (this_max > longest) {
            longest = this_max;
            longest_end = i;
        }
    }

    vector<int> seq{longest_end};
    while (prev[seq.back()] != seq.back()) {
        seq.push_back(prev[seq.back()]);
    }

    cout << seq.size() << endl;
    for (int i = seq.size() - 1; i > 0; i--) {
        cout << seq[i] + 1 << ' ';
    }
    cout << seq.front() + 1 << endl;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB answer = 4
2 Correct 1 ms 204 KB answer = 1
3 Correct 0 ms 292 KB answer = 2
4 Correct 1 ms 204 KB answer = 1
5 Correct 1 ms 204 KB answer = 2
6 Correct 0 ms 292 KB answer = 1
7 Correct 0 ms 292 KB answer = 1
8 Correct 0 ms 204 KB answer = 3
9 Correct 1 ms 204 KB answer = 2
10 Correct 1 ms 204 KB answer = 3
11 Correct 1 ms 204 KB answer = 2
12 Correct 1 ms 204 KB answer = 3
13 Correct 0 ms 292 KB answer = 2
14 Correct 0 ms 292 KB answer = 1
15 Correct 1 ms 204 KB answer = 1
16 Correct 0 ms 204 KB answer = 1
17 Correct 1 ms 204 KB answer = 1
18 Correct 1 ms 204 KB answer = 1
19 Correct 1 ms 204 KB answer = 1
20 Correct 1 ms 204 KB answer = 1
21 Correct 1 ms 204 KB answer = 1
22 Correct 170 ms 728 KB answer = 358
23 Correct 159 ms 656 KB answer = 336
24 Correct 155 ms 616 KB answer = 339
25 Correct 153 ms 616 KB answer = 357
26 Correct 167 ms 616 KB answer = 354
27 Correct 144 ms 580 KB answer = 333
28 Correct 145 ms 640 KB answer = 314
29 Correct 152 ms 652 KB answer = 322
30 Correct 160 ms 716 KB answer = 339
31 Correct 183 ms 664 KB answer = 351
32 Correct 133 ms 644 KB answer = 1
33 Correct 150 ms 756 KB answer = 1
34 Correct 133 ms 696 KB answer = 1
35 Correct 142 ms 660 KB answer = 1
36 Correct 136 ms 632 KB answer = 1
37 Correct 105 ms 688 KB answer = 1
38 Correct 103 ms 688 KB answer = 1
39 Correct 105 ms 580 KB answer = 1
40 Correct 106 ms 580 KB answer = 1

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB answer = 4
2 Correct 1 ms 204 KB answer = 1
3 Correct 0 ms 292 KB answer = 2
4 Correct 1 ms 204 KB answer = 1
5 Correct 1 ms 204 KB answer = 2
6 Correct 0 ms 292 KB answer = 1
7 Correct 0 ms 292 KB answer = 1
8 Correct 0 ms 204 KB answer = 3
9 Correct 1 ms 204 KB answer = 2
10 Correct 1 ms 204 KB answer = 3
11 Correct 1 ms 204 KB answer = 2
12 Correct 1 ms 204 KB answer = 3
13 Correct 0 ms 292 KB answer = 2
14 Correct 0 ms 292 KB answer = 1
15 Correct 1 ms 204 KB answer = 1
16 Correct 0 ms 204 KB answer = 1
17 Correct 1 ms 204 KB answer = 1
18 Correct 1 ms 204 KB answer = 1
19 Correct 1 ms 204 KB answer = 1
20 Correct 1 ms 204 KB answer = 1
21 Correct 1 ms 204 KB answer = 1
22 Correct 170 ms 728 KB answer = 358
23 Correct 159 ms 656 KB answer = 336
24 Correct 155 ms 616 KB answer = 339
25 Correct 153 ms 616 KB answer = 357
26 Correct 167 ms 616 KB answer = 354
27 Correct 144 ms 580 KB answer = 333
28 Correct 145 ms 640 KB answer = 314
29 Correct 152 ms 652 KB answer = 322
30 Correct 160 ms 716 KB answer = 339
31 Correct 183 ms 664 KB answer = 351
32 Correct 133 ms 644 KB answer = 1
33 Correct 150 ms 756 KB answer = 1
34 Correct 133 ms 696 KB answer = 1
35 Correct 142 ms 660 KB answer = 1
36 Correct 136 ms 632 KB answer = 1
37 Correct 105 ms 688 KB answer = 1
38 Correct 103 ms 688 KB answer = 1
39 Correct 105 ms 580 KB answer = 1
40 Correct 106 ms 580 KB answer = 1
41 Correct 247 ms 2076 KB answer = 6296
42 Correct 248 ms 2080 KB answer = 6267
43 Correct 247 ms 2060 KB answer = 6264
44 Correct 253 ms 2072 KB answer = 6384
45 Correct 249 ms 2072 KB answer = 6272
46 Correct 161 ms 2084 KB answer = 6177
47 Correct 159 ms 2072 KB answer = 6144
48 Correct 158 ms 2116 KB answer = 6272
49 Correct 157 ms 2072 KB answer = 6241
50 Correct 159 ms 2064 KB answer = 6169
51 Correct 85 ms 2116 KB answer = 1
52 Correct 80 ms 2080 KB answer = 1
53 Correct 88 ms 2124 KB answer = 1
54 Correct 78 ms 2116 KB answer = 1
55 Correct 83 ms 2088 KB answer = 1
56 Correct 83 ms 1948 KB answer = 1426
57 Correct 83 ms 2000 KB answer = 1427
58 Correct 82 ms 1936 KB answer = 1428
59 Correct 89 ms 2020 KB answer = 1427

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB answer = 4
2 Correct 1 ms 204 KB answer = 1
3 Correct 0 ms 292 KB answer = 2
4 Correct 1 ms 204 KB answer = 1
5 Correct 1 ms 204 KB answer = 2
6 Correct 0 ms 292 KB answer = 1
7 Correct 0 ms 292 KB answer = 1
8 Correct 0 ms 204 KB answer = 3
9 Correct 1 ms 204 KB answer = 2
10 Correct 1 ms 204 KB answer = 3
11 Correct 1 ms 204 KB answer = 2
12 Correct 1 ms 204 KB answer = 3
13 Correct 0 ms 292 KB answer = 2
14 Correct 0 ms 292 KB answer = 1
15 Correct 1 ms 204 KB answer = 1
16 Correct 0 ms 204 KB answer = 1
17 Correct 1 ms 204 KB answer = 1
18 Correct 1 ms 204 KB answer = 1
19 Correct 1 ms 204 KB answer = 1
20 Correct 1 ms 204 KB answer = 1
21 Correct 1 ms 204 KB answer = 1
22 Correct 170 ms 728 KB answer = 358
23 Correct 159 ms 656 KB answer = 336
24 Correct 155 ms 616 KB answer = 339
25 Correct 153 ms 616 KB answer = 357
26 Correct 167 ms 616 KB answer = 354
27 Correct 144 ms 580 KB answer = 333
28 Correct 145 ms 640 KB answer = 314
29 Correct 152 ms 652 KB answer = 322
30 Correct 160 ms 716 KB answer = 339
31 Correct 183 ms 664 KB answer = 351
32 Correct 133 ms 644 KB answer = 1
33 Correct 150 ms 756 KB answer = 1
34 Correct 133 ms 696 KB answer = 1
35 Correct 142 ms 660 KB answer = 1
36 Correct 136 ms 632 KB answer = 1
37 Correct 105 ms 688 KB answer = 1
38 Correct 103 ms 688 KB answer = 1
39 Correct 105 ms 580 KB answer = 1
40 Correct 106 ms 580 KB answer = 1
41 Correct 247 ms 2076 KB answer = 6296
42 Correct 248 ms 2080 KB answer = 6267
43 Correct 247 ms 2060 KB answer = 6264
44 Correct 253 ms 2072 KB answer = 6384
45 Correct 249 ms 2072 KB answer = 6272
46 Correct 161 ms 2084 KB answer = 6177
47 Correct 159 ms 2072 KB answer = 6144
48 Correct 158 ms 2116 KB answer = 6272
49 Correct 157 ms 2072 KB answer = 6241
50 Correct 159 ms 2064 KB answer = 6169
51 Correct 85 ms 2116 KB answer = 1
52 Correct 80 ms 2080 KB answer = 1
53 Correct 88 ms 2124 KB answer = 1
54 Correct 78 ms 2116 KB answer = 1
55 Correct 83 ms 2088 KB answer = 1
56 Correct 83 ms 1948 KB answer = 1426
57 Correct 83 ms 2000 KB answer = 1427
58 Correct 82 ms 1936 KB answer = 1428
59 Correct 89 ms 2020 KB answer = 1427
60 Execution timed out 6005 ms 4148 KB Time limit exceeded
61 Halted 0 ms 0 KB -