oj.uz

Submission #225432

# Submission time Handle Problem Language Result Execution time Memory
225432 2020-04-20T14:47:38 Z emil_physmath Nice sequence (IZhO18_sequence) C++17
100 / 100
 1506 ms 73292 KB 
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
typedef double ldouble;
typedef long long llong;
typedef unsigned int uint;
const int maxN = 100001;

vector<int> nei[400001];
int a[400001];
bool used[400001];

void DFS(int v, vector<int>& order)
{
    used[v] = true;
    for (int to: nei[v])
        if (!used[to])
            DFS(to, order);
    order.push_back(v);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        int len = 0;
        int i = 0;
        do {
            len = max(len, i += n);
            while (i - m >= 0) i -= m;
        } while (i);
        --len;
        for (int i = 0; i <= len; ++i)
        {
            used[i] = a[i] = 0;
            nei[i].clear();
        }
        for (int i = 1; i <= len; ++i)
        {
            if (i - n >= 0)
                nei[i].push_back(i - n);
            if (i - m >= 0)
                nei[i - m].push_back(i);
        }
        vector<int> order;
        for (int i = 0; i <= len; ++i)
            if (!used[i])
                DFS(i, order);
        reverse(order.begin(), order.end());
        vector<int> pref(len + 1);
        for (int i = 0; i < order.size(); ++i)
            pref[order[i]] = i;
        for (int i = 1; i < pref.size(); ++i)
            pref[i] -= pref[0];
        pref[0] = 0;
        for (int i = 1; i <= len; ++i)
            a[i] = pref[i] - pref[i - 1];
        cout << len << endl;
        for (int i = 1; i <= len; ++i)
            cout << a[i] << ' ';
        cout << '\n';
    }
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:44:28: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
             used[i] = a[i] = 0;
                       ~~~~~^~~
sequence.cpp:60:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < order.size(); ++i)
                         ~~^~~~~~~~~~~~~~
sequence.cpp:62:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 1; i < pref.size(); ++i)
                         ~~^~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Ok
2 Correct 10 ms 9728 KB Ok
3 Correct 10 ms 9728 KB Ok
4 Correct 10 ms 9728 KB Ok
5 Correct 10 ms 9728 KB Ok
6 Correct 10 ms 9728 KB Ok
7 Correct 12 ms 9728 KB Ok
8 Correct 10 ms 9728 KB Ok
9 Correct 11 ms 9728 KB Ok
10 Correct 10 ms 9728 KB Ok
11 Correct 10 ms 9728 KB Ok
12 Correct 10 ms 9776 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Ok
2 Correct 12 ms 9776 KB Ok
3 Correct 13 ms 9728 KB Ok
4 Correct 10 ms 9728 KB Ok
5 Correct 12 ms 9728 KB Ok
6 Correct 11 ms 9984 KB Ok
7 Correct 19 ms 10748 KB Ok
8 Correct 16 ms 10240 KB Ok
9 Correct 22 ms 11008 KB Ok
10 Correct 16 ms 10368 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Ok
2 Correct 13 ms 9728 KB Ok
3 Correct 9 ms 9728 KB Ok
4 Correct 10 ms 9728 KB Ok
5 Correct 10 ms 9728 KB Ok
6 Correct 10 ms 9728 KB Ok
7 Correct 9 ms 9728 KB Ok
8 Correct 10 ms 9728 KB Ok
9 Correct 10 ms 9728 KB Ok
10 Correct 10 ms 9728 KB Ok
11 Correct 11 ms 9728 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Ok
2 Correct 10 ms 9728 KB Ok
3 Correct 10 ms 9728 KB Ok
4 Correct 12 ms 9728 KB Ok
5 Correct 10 ms 9728 KB Ok
6 Correct 122 ms 27380 KB Ok
7 Correct 115 ms 26936 KB Ok
8 Correct 187 ms 30656 KB Ok
9 Correct 167 ms 27200 KB Ok
10 Correct 96 ms 21876 KB Ok
11 Correct 162 ms 32796 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Ok
2 Correct 10 ms 9728 KB Ok
3 Correct 10 ms 9728 KB Ok
4 Correct 10 ms 9728 KB Ok
5 Correct 10 ms 9728 KB Ok
6 Correct 10 ms 9728 KB Ok
7 Correct 12 ms 9728 KB Ok
8 Correct 10 ms 9728 KB Ok
9 Correct 11 ms 9728 KB Ok
10 Correct 10 ms 9728 KB Ok
11 Correct 10 ms 9728 KB Ok
12 Correct 10 ms 9776 KB Ok
13 Correct 10 ms 9728 KB Ok
14 Correct 13 ms 9728 KB Ok
15 Correct 9 ms 9728 KB Ok
16 Correct 10 ms 9728 KB Ok
17 Correct 10 ms 9728 KB Ok
18 Correct 10 ms 9728 KB Ok
19 Correct 9 ms 9728 KB Ok
20 Correct 10 ms 9728 KB Ok
21 Correct 10 ms 9728 KB Ok
22 Correct 10 ms 9728 KB Ok
23 Correct 11 ms 9728 KB Ok
24 Correct 13 ms 9984 KB Ok
25 Correct 11 ms 9984 KB Ok
26 Correct 14 ms 9984 KB Ok
27 Correct 11 ms 9984 KB Ok
28 Correct 11 ms 9856 KB Ok
29 Correct 12 ms 9984 KB Ok
30 Correct 11 ms 9856 KB Ok
31 Correct 12 ms 9984 KB Ok
32 Correct 12 ms 9856 KB Ok
33 Correct 12 ms 9984 KB Ok
34 Correct 20 ms 10108 KB Ok
35 Correct 13 ms 10240 KB Ok
36 Correct 14 ms 10240 KB Ok
37 Correct 15 ms 10240 KB Ok
38 Correct 13 ms 10240 KB Ok
39 Correct 14 ms 10240 KB Ok
40 Correct 14 ms 10240 KB Ok
41 Correct 17 ms 10240 KB Ok
42 Correct 14 ms 10240 KB Ok
43 Correct 14 ms 10240 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Ok
2 Correct 10 ms 9728 KB Ok
3 Correct 10 ms 9728 KB Ok
4 Correct 10 ms 9728 KB Ok
5 Correct 10 ms 9728 KB Ok
6 Correct 10 ms 9728 KB Ok
7 Correct 12 ms 9728 KB Ok
8 Correct 10 ms 9728 KB Ok
9 Correct 11 ms 9728 KB Ok
10 Correct 10 ms 9728 KB Ok
11 Correct 10 ms 9728 KB Ok
12 Correct 10 ms 9776 KB Ok
13 Correct 10 ms 9728 KB Ok
14 Correct 12 ms 9776 KB Ok
15 Correct 13 ms 9728 KB Ok
16 Correct 10 ms 9728 KB Ok
17 Correct 12 ms 9728 KB Ok
18 Correct 11 ms 9984 KB Ok
19 Correct 19 ms 10748 KB Ok
20 Correct 16 ms 10240 KB Ok
21 Correct 22 ms 11008 KB Ok
22 Correct 16 ms 10368 KB Ok
23 Correct 10 ms 9728 KB Ok
24 Correct 13 ms 9728 KB Ok
25 Correct 9 ms 9728 KB Ok
26 Correct 10 ms 9728 KB Ok
27 Correct 10 ms 9728 KB Ok
28 Correct 10 ms 9728 KB Ok
29 Correct 9 ms 9728 KB Ok
30 Correct 10 ms 9728 KB Ok
31 Correct 10 ms 9728 KB Ok
32 Correct 10 ms 9728 KB Ok
33 Correct 11 ms 9728 KB Ok
34 Correct 13 ms 9984 KB Ok
35 Correct 11 ms 9984 KB Ok
36 Correct 14 ms 9984 KB Ok
37 Correct 11 ms 9984 KB Ok
38 Correct 11 ms 9856 KB Ok
39 Correct 12 ms 9984 KB Ok
40 Correct 11 ms 9856 KB Ok
41 Correct 12 ms 9984 KB Ok
42 Correct 12 ms 9856 KB Ok
43 Correct 12 ms 9984 KB Ok
44 Correct 20 ms 10108 KB Ok
45 Correct 13 ms 10240 KB Ok
46 Correct 14 ms 10240 KB Ok
47 Correct 15 ms 10240 KB Ok
48 Correct 13 ms 10240 KB Ok
49 Correct 14 ms 10240 KB Ok
50 Correct 14 ms 10240 KB Ok
51 Correct 17 ms 10240 KB Ok
52 Correct 14 ms 10240 KB Ok
53 Correct 14 ms 10240 KB Ok
54 Correct 88 ms 16120 KB Ok
55 Correct 101 ms 16436 KB Ok
56 Correct 110 ms 16260 KB Ok
57 Correct 73 ms 15268 KB Ok
58 Correct 101 ms 16196 KB Ok
59 Correct 86 ms 15864 KB Ok
60 Correct 74 ms 15500 KB Ok
61 Correct 80 ms 15724 KB Ok
62 Correct 105 ms 16656 KB Ok
63 Correct 85 ms 15540 KB Ok
64 Correct 101 ms 16436 KB Ok
65 Correct 96 ms 16376 KB Ok
66 Correct 95 ms 16000 KB Ok
67 Correct 81 ms 15596 KB Ok
68 Correct 90 ms 16024 KB Ok
69 Correct 220 ms 25272 KB Ok
70 Correct 271 ms 24852 KB Ok
71 Correct 180 ms 22764 KB Ok
72 Correct 194 ms 24964 KB Ok
73 Correct 267 ms 23068 KB Ok
74 Correct 208 ms 24028 KB Ok
75 Correct 184 ms 24544 KB Ok
76 Correct 226 ms 24856 KB Ok
77 Correct 201 ms 23548 KB Ok
78 Correct 227 ms 24980 KB Ok
79 Correct 259 ms 24104 KB Ok
80 Correct 226 ms 22896 KB Ok
81 Correct 221 ms 24840 KB Ok
82 Correct 216 ms 24080 KB Ok
83 Correct 204 ms 24952 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Ok
2 Correct 10 ms 9728 KB Ok
3 Correct 10 ms 9728 KB Ok
4 Correct 10 ms 9728 KB Ok
5 Correct 10 ms 9728 KB Ok
6 Correct 10 ms 9728 KB Ok
7 Correct 12 ms 9728 KB Ok
8 Correct 10 ms 9728 KB Ok
9 Correct 11 ms 9728 KB Ok
10 Correct 10 ms 9728 KB Ok
11 Correct 10 ms 9728 KB Ok
12 Correct 10 ms 9776 KB Ok
13 Correct 10 ms 9728 KB Ok
14 Correct 12 ms 9776 KB Ok
15 Correct 13 ms 9728 KB Ok
16 Correct 10 ms 9728 KB Ok
17 Correct 12 ms 9728 KB Ok
18 Correct 11 ms 9984 KB Ok
19 Correct 19 ms 10748 KB Ok
20 Correct 16 ms 10240 KB Ok
21 Correct 22 ms 11008 KB Ok
22 Correct 16 ms 10368 KB Ok
23 Correct 10 ms 9728 KB Ok
24 Correct 13 ms 9728 KB Ok
25 Correct 9 ms 9728 KB Ok
26 Correct 10 ms 9728 KB Ok
27 Correct 10 ms 9728 KB Ok
28 Correct 10 ms 9728 KB Ok
29 Correct 9 ms 9728 KB Ok
30 Correct 10 ms 9728 KB Ok
31 Correct 10 ms 9728 KB Ok
32 Correct 10 ms 9728 KB Ok
33 Correct 11 ms 9728 KB Ok
34 Correct 9 ms 9728 KB Ok
35 Correct 10 ms 9728 KB Ok
36 Correct 10 ms 9728 KB Ok
37 Correct 12 ms 9728 KB Ok
38 Correct 10 ms 9728 KB Ok
39 Correct 122 ms 27380 KB Ok
40 Correct 115 ms 26936 KB Ok
41 Correct 187 ms 30656 KB Ok
42 Correct 167 ms 27200 KB Ok
43 Correct 96 ms 21876 KB Ok
44 Correct 162 ms 32796 KB Ok
45 Correct 13 ms 9984 KB Ok
46 Correct 11 ms 9984 KB Ok
47 Correct 14 ms 9984 KB Ok
48 Correct 11 ms 9984 KB Ok
49 Correct 11 ms 9856 KB Ok
50 Correct 12 ms 9984 KB Ok
51 Correct 11 ms 9856 KB Ok
52 Correct 12 ms 9984 KB Ok
53 Correct 12 ms 9856 KB Ok
54 Correct 12 ms 9984 KB Ok
55 Correct 20 ms 10108 KB Ok
56 Correct 13 ms 10240 KB Ok
57 Correct 14 ms 10240 KB Ok
58 Correct 15 ms 10240 KB Ok
59 Correct 13 ms 10240 KB Ok
60 Correct 14 ms 10240 KB Ok
61 Correct 14 ms 10240 KB Ok
62 Correct 17 ms 10240 KB Ok
63 Correct 14 ms 10240 KB Ok
64 Correct 14 ms 10240 KB Ok
65 Correct 88 ms 16120 KB Ok
66 Correct 101 ms 16436 KB Ok
67 Correct 110 ms 16260 KB Ok
68 Correct 73 ms 15268 KB Ok
69 Correct 101 ms 16196 KB Ok
70 Correct 86 ms 15864 KB Ok
71 Correct 74 ms 15500 KB Ok
72 Correct 80 ms 15724 KB Ok
73 Correct 105 ms 16656 KB Ok
74 Correct 85 ms 15540 KB Ok
75 Correct 101 ms 16436 KB Ok
76 Correct 96 ms 16376 KB Ok
77 Correct 95 ms 16000 KB Ok
78 Correct 81 ms 15596 KB Ok
79 Correct 90 ms 16024 KB Ok
80 Correct 220 ms 25272 KB Ok
81 Correct 271 ms 24852 KB Ok
82 Correct 180 ms 22764 KB Ok
83 Correct 194 ms 24964 KB Ok
84 Correct 267 ms 23068 KB Ok
85 Correct 208 ms 24028 KB Ok
86 Correct 184 ms 24544 KB Ok
87 Correct 226 ms 24856 KB Ok
88 Correct 201 ms 23548 KB Ok
89 Correct 227 ms 24980 KB Ok
90 Correct 259 ms 24104 KB Ok
91 Correct 226 ms 22896 KB Ok
92 Correct 221 ms 24840 KB Ok
93 Correct 216 ms 24080 KB Ok
94 Correct 204 ms 24952 KB Ok
95 Correct 220 ms 25960 KB Ok
96 Correct 312 ms 34080 KB Ok
97 Correct 318 ms 29644 KB Ok
98 Correct 212 ms 28784 KB Ok
99 Correct 257 ms 28676 KB Ok
100 Correct 263 ms 29108 KB Ok
101 Correct 286 ms 32116 KB Ok
102 Correct 253 ms 30804 KB Ok
103 Correct 261 ms 30736 KB Ok
104 Correct 301 ms 32136 KB Ok
105 Correct 290 ms 34024 KB Ok
106 Correct 247 ms 31648 KB Ok
107 Correct 285 ms 32176 KB Ok
108 Correct 331 ms 34168 KB Ok
109 Correct 277 ms 33048 KB Ok
110 Correct 1101 ms 72412 KB Ok
111 Correct 1344 ms 73292 KB Ok
112 Correct 1279 ms 66748 KB Ok
113 Correct 1258 ms 72248 KB Ok
114 Correct 1356 ms 65604 KB Ok
115 Correct 1418 ms 73184 KB Ok
116 Correct 1392 ms 72088 KB Ok
117 Correct 1279 ms 72996 KB Ok
118 Correct 1143 ms 64096 KB Ok
119 Correct 1409 ms 72444 KB Ok
120 Correct 1332 ms 73264 KB Ok
121 Correct 1119 ms 69764 KB Ok
122 Correct 1362 ms 73004 KB Ok
123 Correct 1331 ms 70296 KB Ok
124 Correct 1506 ms 65804 KB Ok
125 Correct 525 ms 56764 KB Ok