oj.uz

Submission #497949

# Submission time Handle Problem Language Result Execution time Memory
497949 2021-12-24T05:53:04 Z kingline Nice sequence (IZhO18_sequence) C++17
100 / 100
 1218 ms 91264 KB 
/*#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")*/
#include <bits/stdc++.h>
#pragma GCC optimize ("unroll-loops,Ofast,O3")
#pragma GCC target("avx,avx2,fma")
//#define file(data) freopen(data".in", "r", stdin); freopen(data".out", "w", stdout);
#define pb push_back
//#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(data) data.begin() , data.end()
#define endl '\n'
//freopen("nenokku_easy.in", "r", stdin);
//freopen("nenokku_easy.out", "w", stdout);
#define int long long
#define pii pair < int, int >
#define pll pair < long long, long long >

using namespace std;

typedef long long ll;
const int N = 1e6 + 5;
const int M = 305;
const int mod = 1e9 + 7;

int q, n, m, used[N], state, cl[N], ms[N];
vector < int > g[N], arr;

void topsort(int v) {
    used[v] = 1;
    for(int i = 0; i < g[v].size(); i++) {
        int to = g[v][i];
        if(!used[to]) {
            topsort(to);
        }
    }
    arr.pb(v);
}

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //file("pieaters");
    cin >> q;
    while(q--) {
        cin >> n >> m;
        int sz = n + m - 1 - __gcd(n, m);
        cout << sz << endl;
        for(int i = 0; i <= sz; i++) {
            if(i - n >= 0) {
                g[i].pb(i - n);
            }
            if(i + m <= sz) {
                g[i].pb(i + m);
            }
        }
        for(int i = 0; i <= sz; i++) {
            if(!used[i]) {
                topsort(i);
            }
        }
        reverse(all(arr));
        for(int i = 0; i < arr.size(); i++) {
            //cout << arr[i] << " ";
            ms[arr[i]] = i;
        }
        //cout << endl;
        int val = ms[0];
        ms[0] = 0;
        for(int i = 1; i <= sz; i++) {
            ms[i] -= val;
            cout << ms[i] - ms[i - 1] << " ";
        }
        cout << endl;
        if(arr.size()) arr.clear();
        for(int i = 0; i <= sz; i++) {
            if(g[i].size()) g[i].clear();
            used[i] = 0;
        }
    }
}

Compilation message

sequence.cpp: In function 'void topsort(long long int)':
sequence.cpp:32:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i = 0; i < g[v].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
sequence.cpp: At global scope:
sequence.cpp:41:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   41 | main() {
      | ^~~~
sequence.cpp: In function 'int main()':
sequence.cpp:65:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(int i = 0; i < arr.size(); i++) {
      |                        ~~^~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Ok
2 Correct 12 ms 23808 KB Ok
3 Correct 14 ms 23756 KB Ok
4 Correct 11 ms 23756 KB Ok
5 Correct 11 ms 23756 KB Ok
6 Correct 11 ms 23692 KB Ok
7 Correct 12 ms 23692 KB Ok
8 Correct 14 ms 23796 KB Ok
9 Correct 11 ms 23756 KB Ok
10 Correct 15 ms 23756 KB Ok
11 Correct 15 ms 23716 KB Ok
12 Correct 14 ms 23756 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Ok
2 Correct 11 ms 23708 KB Ok
3 Correct 11 ms 23756 KB Ok
4 Correct 12 ms 23784 KB Ok
5 Correct 13 ms 23912 KB Ok
6 Correct 18 ms 24012 KB Ok
7 Correct 19 ms 24920 KB Ok
8 Correct 16 ms 24288 KB Ok
9 Correct 23 ms 25152 KB Ok
10 Correct 18 ms 24524 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Ok
2 Correct 11 ms 23696 KB Ok
3 Correct 12 ms 23812 KB Ok
4 Correct 12 ms 23756 KB Ok
5 Correct 12 ms 23816 KB Ok
6 Correct 13 ms 23804 KB Ok
7 Correct 12 ms 23756 KB Ok
8 Correct 13 ms 23740 KB Ok
9 Correct 16 ms 23728 KB Ok
10 Correct 12 ms 23724 KB Ok
11 Correct 12 ms 23776 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23696 KB Ok
2 Correct 15 ms 23756 KB Ok
3 Correct 12 ms 23708 KB Ok
4 Correct 12 ms 23808 KB Ok
5 Correct 14 ms 23756 KB Ok
6 Correct 90 ms 43596 KB Ok
7 Correct 81 ms 43524 KB Ok
8 Correct 130 ms 46804 KB Ok
9 Correct 113 ms 42632 KB Ok
10 Correct 72 ms 37308 KB Ok
11 Correct 108 ms 48592 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Ok
2 Correct 12 ms 23808 KB Ok
3 Correct 14 ms 23756 KB Ok
4 Correct 11 ms 23756 KB Ok
5 Correct 11 ms 23756 KB Ok
6 Correct 11 ms 23692 KB Ok
7 Correct 12 ms 23692 KB Ok
8 Correct 14 ms 23796 KB Ok
9 Correct 11 ms 23756 KB Ok
10 Correct 15 ms 23756 KB Ok
11 Correct 15 ms 23716 KB Ok
12 Correct 14 ms 23756 KB Ok
13 Correct 12 ms 23756 KB Ok
14 Correct 11 ms 23696 KB Ok
15 Correct 12 ms 23812 KB Ok
16 Correct 12 ms 23756 KB Ok
17 Correct 12 ms 23816 KB Ok
18 Correct 13 ms 23804 KB Ok
19 Correct 12 ms 23756 KB Ok
20 Correct 13 ms 23740 KB Ok
21 Correct 16 ms 23728 KB Ok
22 Correct 12 ms 23724 KB Ok
23 Correct 12 ms 23776 KB Ok
24 Correct 14 ms 24012 KB Ok
25 Correct 18 ms 24060 KB Ok
26 Correct 20 ms 24012 KB Ok
27 Correct 14 ms 24044 KB Ok
28 Correct 14 ms 23904 KB Ok
29 Correct 13 ms 23928 KB Ok
30 Correct 13 ms 23884 KB Ok
31 Correct 13 ms 23952 KB Ok
32 Correct 14 ms 24032 KB Ok
33 Correct 14 ms 24012 KB Ok
34 Correct 15 ms 24268 KB Ok
35 Correct 17 ms 24216 KB Ok
36 Correct 17 ms 24336 KB Ok
37 Correct 18 ms 24276 KB Ok
38 Correct 16 ms 24252 KB Ok
39 Correct 15 ms 24268 KB Ok
40 Correct 15 ms 24268 KB Ok
41 Correct 15 ms 24268 KB Ok
42 Correct 16 ms 24384 KB Ok
43 Correct 16 ms 24268 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Ok
2 Correct 12 ms 23808 KB Ok
3 Correct 14 ms 23756 KB Ok
4 Correct 11 ms 23756 KB Ok
5 Correct 11 ms 23756 KB Ok
6 Correct 11 ms 23692 KB Ok
7 Correct 12 ms 23692 KB Ok
8 Correct 14 ms 23796 KB Ok
9 Correct 11 ms 23756 KB Ok
10 Correct 15 ms 23756 KB Ok
11 Correct 15 ms 23716 KB Ok
12 Correct 14 ms 23756 KB Ok
13 Correct 12 ms 23756 KB Ok
14 Correct 11 ms 23708 KB Ok
15 Correct 11 ms 23756 KB Ok
16 Correct 12 ms 23784 KB Ok
17 Correct 13 ms 23912 KB Ok
18 Correct 18 ms 24012 KB Ok
19 Correct 19 ms 24920 KB Ok
20 Correct 16 ms 24288 KB Ok
21 Correct 23 ms 25152 KB Ok
22 Correct 18 ms 24524 KB Ok
23 Correct 12 ms 23756 KB Ok
24 Correct 11 ms 23696 KB Ok
25 Correct 12 ms 23812 KB Ok
26 Correct 12 ms 23756 KB Ok
27 Correct 12 ms 23816 KB Ok
28 Correct 13 ms 23804 KB Ok
29 Correct 12 ms 23756 KB Ok
30 Correct 13 ms 23740 KB Ok
31 Correct 16 ms 23728 KB Ok
32 Correct 12 ms 23724 KB Ok
33 Correct 12 ms 23776 KB Ok
34 Correct 14 ms 24012 KB Ok
35 Correct 18 ms 24060 KB Ok
36 Correct 20 ms 24012 KB Ok
37 Correct 14 ms 24044 KB Ok
38 Correct 14 ms 23904 KB Ok
39 Correct 13 ms 23928 KB Ok
40 Correct 13 ms 23884 KB Ok
41 Correct 13 ms 23952 KB Ok
42 Correct 14 ms 24032 KB Ok
43 Correct 14 ms 24012 KB Ok
44 Correct 15 ms 24268 KB Ok
45 Correct 17 ms 24216 KB Ok
46 Correct 17 ms 24336 KB Ok
47 Correct 18 ms 24276 KB Ok
48 Correct 16 ms 24252 KB Ok
49 Correct 15 ms 24268 KB Ok
50 Correct 15 ms 24268 KB Ok
51 Correct 15 ms 24268 KB Ok
52 Correct 16 ms 24384 KB Ok
53 Correct 16 ms 24268 KB Ok
54 Correct 75 ms 31008 KB Ok
55 Correct 80 ms 31440 KB Ok
56 Correct 74 ms 31356 KB Ok
57 Correct 59 ms 30144 KB Ok
58 Correct 83 ms 31256 KB Ok
59 Correct 69 ms 30740 KB Ok
60 Correct 66 ms 30124 KB Ok
61 Correct 63 ms 30740 KB Ok
62 Correct 77 ms 31624 KB Ok
63 Correct 68 ms 30448 KB Ok
64 Correct 74 ms 31296 KB Ok
65 Correct 81 ms 31248 KB Ok
66 Correct 85 ms 30872 KB Ok
67 Correct 56 ms 30396 KB Ok
68 Correct 72 ms 31044 KB Ok
69 Correct 168 ms 40008 KB Ok
70 Correct 172 ms 39908 KB Ok
71 Correct 146 ms 37748 KB Ok
72 Correct 203 ms 40208 KB Ok
73 Correct 157 ms 38176 KB Ok
74 Correct 158 ms 39096 KB Ok
75 Correct 158 ms 39640 KB Ok
76 Correct 171 ms 39876 KB Ok
77 Correct 152 ms 38716 KB Ok
78 Correct 179 ms 40124 KB Ok
79 Correct 163 ms 39140 KB Ok
80 Correct 156 ms 38040 KB Ok
81 Correct 161 ms 39856 KB Ok
82 Correct 163 ms 39044 KB Ok
83 Correct 153 ms 40032 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Ok
2 Correct 12 ms 23808 KB Ok
3 Correct 14 ms 23756 KB Ok
4 Correct 11 ms 23756 KB Ok
5 Correct 11 ms 23756 KB Ok
6 Correct 11 ms 23692 KB Ok
7 Correct 12 ms 23692 KB Ok
8 Correct 14 ms 23796 KB Ok
9 Correct 11 ms 23756 KB Ok
10 Correct 15 ms 23756 KB Ok
11 Correct 15 ms 23716 KB Ok
12 Correct 14 ms 23756 KB Ok
13 Correct 12 ms 23756 KB Ok
14 Correct 11 ms 23708 KB Ok
15 Correct 11 ms 23756 KB Ok
16 Correct 12 ms 23784 KB Ok
17 Correct 13 ms 23912 KB Ok
18 Correct 18 ms 24012 KB Ok
19 Correct 19 ms 24920 KB Ok
20 Correct 16 ms 24288 KB Ok
21 Correct 23 ms 25152 KB Ok
22 Correct 18 ms 24524 KB Ok
23 Correct 12 ms 23756 KB Ok
24 Correct 11 ms 23696 KB Ok
25 Correct 12 ms 23812 KB Ok
26 Correct 12 ms 23756 KB Ok
27 Correct 12 ms 23816 KB Ok
28 Correct 13 ms 23804 KB Ok
29 Correct 12 ms 23756 KB Ok
30 Correct 13 ms 23740 KB Ok
31 Correct 16 ms 23728 KB Ok
32 Correct 12 ms 23724 KB Ok
33 Correct 12 ms 23776 KB Ok
34 Correct 13 ms 23696 KB Ok
35 Correct 15 ms 23756 KB Ok
36 Correct 12 ms 23708 KB Ok
37 Correct 12 ms 23808 KB Ok
38 Correct 14 ms 23756 KB Ok
39 Correct 90 ms 43596 KB Ok
40 Correct 81 ms 43524 KB Ok
41 Correct 130 ms 46804 KB Ok
42 Correct 113 ms 42632 KB Ok
43 Correct 72 ms 37308 KB Ok
44 Correct 108 ms 48592 KB Ok
45 Correct 14 ms 24012 KB Ok
46 Correct 18 ms 24060 KB Ok
47 Correct 20 ms 24012 KB Ok
48 Correct 14 ms 24044 KB Ok
49 Correct 14 ms 23904 KB Ok
50 Correct 13 ms 23928 KB Ok
51 Correct 13 ms 23884 KB Ok
52 Correct 13 ms 23952 KB Ok
53 Correct 14 ms 24032 KB Ok
54 Correct 14 ms 24012 KB Ok
55 Correct 15 ms 24268 KB Ok
56 Correct 17 ms 24216 KB Ok
57 Correct 17 ms 24336 KB Ok
58 Correct 18 ms 24276 KB Ok
59 Correct 16 ms 24252 KB Ok
60 Correct 15 ms 24268 KB Ok
61 Correct 15 ms 24268 KB Ok
62 Correct 15 ms 24268 KB Ok
63 Correct 16 ms 24384 KB Ok
64 Correct 16 ms 24268 KB Ok
65 Correct 75 ms 31008 KB Ok
66 Correct 80 ms 31440 KB Ok
67 Correct 74 ms 31356 KB Ok
68 Correct 59 ms 30144 KB Ok
69 Correct 83 ms 31256 KB Ok
70 Correct 69 ms 30740 KB Ok
71 Correct 66 ms 30124 KB Ok
72 Correct 63 ms 30740 KB Ok
73 Correct 77 ms 31624 KB Ok
74 Correct 68 ms 30448 KB Ok
75 Correct 74 ms 31296 KB Ok
76 Correct 81 ms 31248 KB Ok
77 Correct 85 ms 30872 KB Ok
78 Correct 56 ms 30396 KB Ok
79 Correct 72 ms 31044 KB Ok
80 Correct 168 ms 40008 KB Ok
81 Correct 172 ms 39908 KB Ok
82 Correct 146 ms 37748 KB Ok
83 Correct 203 ms 40208 KB Ok
84 Correct 157 ms 38176 KB Ok
85 Correct 158 ms 39096 KB Ok
86 Correct 158 ms 39640 KB Ok
87 Correct 171 ms 39876 KB Ok
88 Correct 152 ms 38716 KB Ok
89 Correct 179 ms 40124 KB Ok
90 Correct 163 ms 39140 KB Ok
91 Correct 156 ms 38040 KB Ok
92 Correct 161 ms 39856 KB Ok
93 Correct 163 ms 39044 KB Ok
94 Correct 153 ms 40032 KB Ok
95 Correct 154 ms 42620 KB Ok
96 Correct 236 ms 51868 KB Ok
97 Correct 208 ms 46844 KB Ok
98 Correct 162 ms 46644 KB Ok
99 Correct 193 ms 46028 KB Ok
100 Correct 194 ms 46120 KB Ok
101 Correct 198 ms 49168 KB Ok
102 Correct 195 ms 47072 KB Ok
103 Correct 190 ms 48552 KB Ok
104 Correct 224 ms 50272 KB Ok
105 Correct 219 ms 51168 KB Ok
106 Correct 182 ms 50432 KB Ok
107 Correct 201 ms 49804 KB Ok
108 Correct 235 ms 51248 KB Ok
109 Correct 215 ms 52208 KB Ok
110 Correct 967 ms 90252 KB Ok
111 Correct 1194 ms 91264 KB Ok
112 Correct 1160 ms 84396 KB Ok
113 Correct 988 ms 90024 KB Ok
114 Correct 1109 ms 83240 KB Ok
115 Correct 1218 ms 91024 KB Ok
116 Correct 1150 ms 89960 KB Ok
117 Correct 1064 ms 91072 KB Ok
118 Correct 1130 ms 81776 KB Ok
119 Correct 1146 ms 90160 KB Ok
120 Correct 1092 ms 91024 KB Ok
121 Correct 1046 ms 87720 KB Ok
122 Correct 1044 ms 90732 KB Ok
123 Correct 1202 ms 87744 KB Ok
124 Correct 1053 ms 83608 KB Ok
125 Correct 357 ms 74644 KB Ok