oj.uz

Submission #497948

# Submission time Handle Problem Language Result Execution time Memory
497948 2021-12-24T05:51:14 Z kingline Nice sequence (IZhO18_sequence) C++17
76 / 100
 202 ms 33160 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 = 2e5 + 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;
        arr.clear();
        for(int i = 0; i <= sz; i++) {
            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 3 ms 4940 KB Ok
2 Correct 2 ms 4940 KB Ok
3 Correct 4 ms 4940 KB Ok
4 Correct 3 ms 4960 KB Ok
5 Correct 3 ms 4940 KB Ok
6 Correct 3 ms 4940 KB Ok
7 Correct 3 ms 4940 KB Ok
8 Correct 3 ms 4940 KB Ok
9 Correct 3 ms 4940 KB Ok
10 Correct 2 ms 4940 KB Ok
11 Correct 2 ms 4940 KB Ok
12 Correct 2 ms 4940 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Ok
2 Correct 2 ms 4940 KB Ok
3 Correct 2 ms 4940 KB Ok
4 Correct 2 ms 4940 KB Ok
5 Correct 2 ms 4940 KB Ok
6 Correct 3 ms 5196 KB Ok
7 Correct 10 ms 6108 KB Ok
8 Correct 6 ms 5452 KB Ok
9 Correct 12 ms 6348 KB Ok
10 Correct 7 ms 5776 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Ok
2 Correct 3 ms 4940 KB Ok
3 Correct 3 ms 4940 KB Ok
4 Correct 3 ms 4940 KB Ok
5 Correct 3 ms 4940 KB Ok
6 Correct 87 ms 24884 KB Ok
7 Correct 87 ms 24680 KB Ok
8 Correct 123 ms 28004 KB Ok
9 Correct 105 ms 23856 KB Ok
10 Correct 62 ms 18624 KB Ok
11 Correct 101 ms 29872 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Ok
2 Correct 2 ms 4940 KB Ok
3 Correct 4 ms 4940 KB Ok
4 Correct 3 ms 4960 KB Ok
5 Correct 3 ms 4940 KB Ok
6 Correct 3 ms 4940 KB Ok
7 Correct 3 ms 4940 KB Ok
8 Correct 3 ms 4940 KB Ok
9 Correct 3 ms 4940 KB Ok
10 Correct 2 ms 4940 KB Ok
11 Correct 2 ms 4940 KB Ok
12 Correct 2 ms 4940 KB Ok
13 Correct 3 ms 4940 KB Ok
14 Correct 2 ms 4940 KB Ok
15 Correct 2 ms 4940 KB Ok
16 Correct 2 ms 4940 KB Ok
17 Correct 3 ms 4940 KB Ok
18 Correct 2 ms 4940 KB Ok
19 Correct 2 ms 4940 KB Ok
20 Correct 3 ms 4940 KB Ok
21 Correct 3 ms 4940 KB Ok
22 Correct 3 ms 4940 KB Ok
23 Correct 4 ms 4940 KB Ok
24 Correct 4 ms 5196 KB Ok
25 Correct 4 ms 5196 KB Ok
26 Correct 4 ms 5196 KB Ok
27 Correct 3 ms 5168 KB Ok
28 Correct 5 ms 5196 KB Ok
29 Correct 4 ms 5196 KB Ok
30 Correct 6 ms 5196 KB Ok
31 Correct 4 ms 5228 KB Ok
32 Correct 5 ms 5196 KB Ok
33 Correct 4 ms 5196 KB Ok
34 Correct 6 ms 5452 KB Ok
35 Correct 6 ms 5452 KB Ok
36 Correct 6 ms 5580 KB Ok
37 Correct 5 ms 5452 KB Ok
38 Correct 5 ms 5448 KB Ok
39 Correct 6 ms 5452 KB Ok
40 Correct 6 ms 5580 KB Ok
41 Correct 5 ms 5452 KB Ok
42 Correct 5 ms 5580 KB Ok
43 Correct 6 ms 5452 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Ok
2 Correct 2 ms 4940 KB Ok
3 Correct 4 ms 4940 KB Ok
4 Correct 3 ms 4960 KB Ok
5 Correct 3 ms 4940 KB Ok
6 Correct 3 ms 4940 KB Ok
7 Correct 3 ms 4940 KB Ok
8 Correct 3 ms 4940 KB Ok
9 Correct 3 ms 4940 KB Ok
10 Correct 2 ms 4940 KB Ok
11 Correct 2 ms 4940 KB Ok
12 Correct 2 ms 4940 KB Ok
13 Correct 3 ms 4940 KB Ok
14 Correct 2 ms 4940 KB Ok
15 Correct 2 ms 4940 KB Ok
16 Correct 2 ms 4940 KB Ok
17 Correct 2 ms 4940 KB Ok
18 Correct 3 ms 5196 KB Ok
19 Correct 10 ms 6108 KB Ok
20 Correct 6 ms 5452 KB Ok
21 Correct 12 ms 6348 KB Ok
22 Correct 7 ms 5776 KB Ok
23 Correct 3 ms 4940 KB Ok
24 Correct 2 ms 4940 KB Ok
25 Correct 2 ms 4940 KB Ok
26 Correct 2 ms 4940 KB Ok
27 Correct 3 ms 4940 KB Ok
28 Correct 2 ms 4940 KB Ok
29 Correct 2 ms 4940 KB Ok
30 Correct 3 ms 4940 KB Ok
31 Correct 3 ms 4940 KB Ok
32 Correct 3 ms 4940 KB Ok
33 Correct 4 ms 4940 KB Ok
34 Correct 4 ms 5196 KB Ok
35 Correct 4 ms 5196 KB Ok
36 Correct 4 ms 5196 KB Ok
37 Correct 3 ms 5168 KB Ok
38 Correct 5 ms 5196 KB Ok
39 Correct 4 ms 5196 KB Ok
40 Correct 6 ms 5196 KB Ok
41 Correct 4 ms 5228 KB Ok
42 Correct 5 ms 5196 KB Ok
43 Correct 4 ms 5196 KB Ok
44 Correct 6 ms 5452 KB Ok
45 Correct 6 ms 5452 KB Ok
46 Correct 6 ms 5580 KB Ok
47 Correct 5 ms 5452 KB Ok
48 Correct 5 ms 5448 KB Ok
49 Correct 6 ms 5452 KB Ok
50 Correct 6 ms 5580 KB Ok
51 Correct 5 ms 5452 KB Ok
52 Correct 5 ms 5580 KB Ok
53 Correct 6 ms 5452 KB Ok
54 Correct 59 ms 12088 KB Ok
55 Correct 65 ms 12604 KB Ok
56 Correct 66 ms 12564 KB Ok
57 Correct 53 ms 11416 KB Ok
58 Correct 70 ms 12352 KB Ok
59 Correct 58 ms 11956 KB Ok
60 Correct 53 ms 11316 KB Ok
61 Correct 50 ms 11840 KB Ok
62 Correct 87 ms 12804 KB Ok
63 Correct 55 ms 11708 KB Ok
64 Correct 75 ms 12596 KB Ok
65 Correct 61 ms 12352 KB Ok
66 Correct 57 ms 12092 KB Ok
67 Correct 49 ms 11688 KB Ok
68 Correct 58 ms 12276 KB Ok
69 Correct 152 ms 21168 KB Ok
70 Correct 182 ms 21076 KB Ok
71 Correct 137 ms 19000 KB Ok
72 Correct 153 ms 21176 KB Ok
73 Correct 163 ms 19384 KB Ok
74 Correct 159 ms 20212 KB Ok
75 Correct 163 ms 20816 KB Ok
76 Correct 167 ms 21172 KB Ok
77 Correct 142 ms 19864 KB Ok
78 Correct 202 ms 21208 KB Ok
79 Correct 161 ms 20396 KB Ok
80 Correct 161 ms 19232 KB Ok
81 Correct 159 ms 21052 KB Ok
82 Correct 163 ms 20404 KB Ok
83 Correct 140 ms 21220 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Ok
2 Correct 2 ms 4940 KB Ok
3 Correct 4 ms 4940 KB Ok
4 Correct 3 ms 4960 KB Ok
5 Correct 3 ms 4940 KB Ok
6 Correct 3 ms 4940 KB Ok
7 Correct 3 ms 4940 KB Ok
8 Correct 3 ms 4940 KB Ok
9 Correct 3 ms 4940 KB Ok
10 Correct 2 ms 4940 KB Ok
11 Correct 2 ms 4940 KB Ok
12 Correct 2 ms 4940 KB Ok
13 Correct 3 ms 4940 KB Ok
14 Correct 2 ms 4940 KB Ok
15 Correct 2 ms 4940 KB Ok
16 Correct 2 ms 4940 KB Ok
17 Correct 2 ms 4940 KB Ok
18 Correct 3 ms 5196 KB Ok
19 Correct 10 ms 6108 KB Ok
20 Correct 6 ms 5452 KB Ok
21 Correct 12 ms 6348 KB Ok
22 Correct 7 ms 5776 KB Ok
23 Correct 3 ms 4940 KB Ok
24 Correct 2 ms 4940 KB Ok
25 Correct 2 ms 4940 KB Ok
26 Correct 2 ms 4940 KB Ok
27 Correct 3 ms 4940 KB Ok
28 Correct 2 ms 4940 KB Ok
29 Correct 2 ms 4940 KB Ok
30 Correct 3 ms 4940 KB Ok
31 Correct 3 ms 4940 KB Ok
32 Correct 3 ms 4940 KB Ok
33 Correct 4 ms 4940 KB Ok
34 Correct 3 ms 4940 KB Ok
35 Correct 3 ms 4940 KB Ok
36 Correct 3 ms 4940 KB Ok
37 Correct 3 ms 4940 KB Ok
38 Correct 3 ms 4940 KB Ok
39 Correct 87 ms 24884 KB Ok
40 Correct 87 ms 24680 KB Ok
41 Correct 123 ms 28004 KB Ok
42 Correct 105 ms 23856 KB Ok
43 Correct 62 ms 18624 KB Ok
44 Correct 101 ms 29872 KB Ok
45 Correct 4 ms 5196 KB Ok
46 Correct 4 ms 5196 KB Ok
47 Correct 4 ms 5196 KB Ok
48 Correct 3 ms 5168 KB Ok
49 Correct 5 ms 5196 KB Ok
50 Correct 4 ms 5196 KB Ok
51 Correct 6 ms 5196 KB Ok
52 Correct 4 ms 5228 KB Ok
53 Correct 5 ms 5196 KB Ok
54 Correct 4 ms 5196 KB Ok
55 Correct 6 ms 5452 KB Ok
56 Correct 6 ms 5452 KB Ok
57 Correct 6 ms 5580 KB Ok
58 Correct 5 ms 5452 KB Ok
59 Correct 5 ms 5448 KB Ok
60 Correct 6 ms 5452 KB Ok
61 Correct 6 ms 5580 KB Ok
62 Correct 5 ms 5452 KB Ok
63 Correct 5 ms 5580 KB Ok
64 Correct 6 ms 5452 KB Ok
65 Correct 59 ms 12088 KB Ok
66 Correct 65 ms 12604 KB Ok
67 Correct 66 ms 12564 KB Ok
68 Correct 53 ms 11416 KB Ok
69 Correct 70 ms 12352 KB Ok
70 Correct 58 ms 11956 KB Ok
71 Correct 53 ms 11316 KB Ok
72 Correct 50 ms 11840 KB Ok
73 Correct 87 ms 12804 KB Ok
74 Correct 55 ms 11708 KB Ok
75 Correct 75 ms 12596 KB Ok
76 Correct 61 ms 12352 KB Ok
77 Correct 57 ms 12092 KB Ok
78 Correct 49 ms 11688 KB Ok
79 Correct 58 ms 12276 KB Ok
80 Correct 152 ms 21168 KB Ok
81 Correct 182 ms 21076 KB Ok
82 Correct 137 ms 19000 KB Ok
83 Correct 153 ms 21176 KB Ok
84 Correct 163 ms 19384 KB Ok
85 Correct 159 ms 20212 KB Ok
86 Correct 163 ms 20816 KB Ok
87 Correct 167 ms 21172 KB Ok
88 Correct 142 ms 19864 KB Ok
89 Correct 202 ms 21208 KB Ok
90 Correct 161 ms 20396 KB Ok
91 Correct 161 ms 19232 KB Ok
92 Correct 159 ms 21052 KB Ok
93 Correct 163 ms 20404 KB Ok
94 Correct 140 ms 21220 KB Ok
95 Runtime error 68 ms 33160 KB Execution killed with signal 11
96 Halted 0 ms 0 KB -