oj.uz

Submission #496324

# Submission time Handle Problem Language Result Execution time Memory
496324 2021-12-21T05:46:11 Z Nalrimet Nice sequence (IZhO18_sequence) C++17
100 / 100
 1562 ms 110308 KB 
//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>
using namespace std;

const int N = 2 * 1e6 + 5;
const long long inf = 1000000000;

#define F first
#define S second
#define pb push_back

int n, t, a, b, lastans, k, id, m;
bool used[N];
pair<int, int> pref[N];
vector<int> top, g[N];

void create(int v){
    for(int i = 0; i <= v; ++i){
        g[i].clear();
        used[i] = 0;
    }
    for(int i = 0; i <= v; ++i){
        if(i + n <= v) g[i + n].pb(i);
        if(i - m >= 0) g[i - m].pb(i);
    }
}
/*
0 -> 3 -> 2 1

2 3 0 1
0 1 2 3

2 3 0 1
*/
bool check(int v){
    used[v] = 1;
    for(auto to : g[v]){
        if(used[to] == 1){
            return 1;
        }
        else if(used[to] == 0){
            if(check(to)) return 1;
        }
    }
    used[v] = 2;
    return 0;
}

void topsort(int v){
    used[v] = 1;
    for(auto to : g[v]){
        if(used[to] == 0){
            topsort(to);
        }
    }
    top.pb(v);
}

 main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> t;

    while(t--){
        cin >> n >> m;
        int l = 0, r = n + m , mid;
//        while(l < r){
////            cout << l << ' ' << r << '\n';
//            mid = (l + r) / 2;
//            create(mid);
////            for(int i = 0; i <= mid; ++i){
////                cout << i << '\n';
////                for(auto to : g[i]){
////                    cout << to << ' ';
////                }
////                cout << '\n';
////            }
////            cout << "OK\n";
//            if(!check(mid)) l = mid;
//            else r = mid - 1;
//        }
        l = n + m - 1 - __gcd(n, m);
        cout << l << '\n';
        create(l);
        top.clear();
        for(int i = 0; i <= l; ++i){
            if(!used[i]) topsort(i);
        }
        reverse(top.begin(), top.end());
        for(int i = 0; i < top.size(); ++i){
//            cout << top[i] << ' ' << i << '\n';
            pref[i] = {top[i], i};
        }
//        cout << '\n';
        sort(pref, pref + top.size());
        for(int i = 1; i < top.size(); i++){
            cout << (pref[i].S - pref[i - 1].S) << ' ';
        }
        cout << '\n';
    }

    return 0;

}

// merge sort tree
// l <= b <= r
// r < b

Compilation message

sequence.cpp:65:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   65 |  main() {
      |  ^~~~
sequence.cpp: In function 'int main()':
sequence.cpp:99:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for(int i = 0; i < top.size(); ++i){
      |                        ~~^~~~~~~~~~~~
sequence.cpp:105:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for(int i = 1; i < top.size(); i++){
      |                        ~~^~~~~~~~~~~~
sequence.cpp:75:20: warning: unused variable 'r' [-Wunused-variable]
   75 |         int l = 0, r = n + m , mid;
      |                    ^
sequence.cpp:75:32: warning: unused variable 'mid' [-Wunused-variable]
   75 |         int l = 0, r = n + m , mid;
      |                                ^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47232 KB Ok
2 Correct 24 ms 47304 KB Ok
3 Correct 23 ms 47212 KB Ok
4 Correct 24 ms 47292 KB Ok
5 Correct 22 ms 47272 KB Ok
6 Correct 24 ms 47288 KB Ok
7 Correct 23 ms 47252 KB Ok
8 Correct 24 ms 47204 KB Ok
9 Correct 24 ms 47196 KB Ok
10 Correct 23 ms 47180 KB Ok
11 Correct 24 ms 47240 KB Ok
12 Correct 28 ms 47180 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47220 KB Ok
2 Correct 25 ms 47268 KB Ok
3 Correct 22 ms 47260 KB Ok
4 Correct 23 ms 47180 KB Ok
5 Correct 24 ms 47288 KB Ok
6 Correct 25 ms 47448 KB Ok
7 Correct 36 ms 48324 KB Ok
8 Correct 29 ms 47752 KB Ok
9 Correct 40 ms 48412 KB Ok
10 Correct 32 ms 47944 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47180 KB Ok
2 Correct 26 ms 47180 KB Ok
3 Correct 23 ms 47280 KB Ok
4 Correct 24 ms 47284 KB Ok
5 Correct 28 ms 47196 KB Ok
6 Correct 23 ms 47180 KB Ok
7 Correct 24 ms 47216 KB Ok
8 Correct 25 ms 47220 KB Ok
9 Correct 25 ms 47180 KB Ok
10 Correct 25 ms 47240 KB Ok
11 Correct 24 ms 47308 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47180 KB Ok
2 Correct 24 ms 47264 KB Ok
3 Correct 24 ms 47296 KB Ok
4 Correct 27 ms 47280 KB Ok
5 Correct 24 ms 47288 KB Ok
6 Correct 127 ms 65348 KB Ok
7 Correct 111 ms 64908 KB Ok
8 Correct 188 ms 68216 KB Ok
9 Correct 161 ms 64312 KB Ok
10 Correct 100 ms 59500 KB Ok
11 Correct 157 ms 70124 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47232 KB Ok
2 Correct 24 ms 47304 KB Ok
3 Correct 23 ms 47212 KB Ok
4 Correct 24 ms 47292 KB Ok
5 Correct 22 ms 47272 KB Ok
6 Correct 24 ms 47288 KB Ok
7 Correct 23 ms 47252 KB Ok
8 Correct 24 ms 47204 KB Ok
9 Correct 24 ms 47196 KB Ok
10 Correct 23 ms 47180 KB Ok
11 Correct 24 ms 47240 KB Ok
12 Correct 28 ms 47180 KB Ok
13 Correct 23 ms 47180 KB Ok
14 Correct 26 ms 47180 KB Ok
15 Correct 23 ms 47280 KB Ok
16 Correct 24 ms 47284 KB Ok
17 Correct 28 ms 47196 KB Ok
18 Correct 23 ms 47180 KB Ok
19 Correct 24 ms 47216 KB Ok
20 Correct 25 ms 47220 KB Ok
21 Correct 25 ms 47180 KB Ok
22 Correct 25 ms 47240 KB Ok
23 Correct 24 ms 47308 KB Ok
24 Correct 25 ms 47416 KB Ok
25 Correct 26 ms 47512 KB Ok
26 Correct 25 ms 47424 KB Ok
27 Correct 26 ms 47488 KB Ok
28 Correct 29 ms 47368 KB Ok
29 Correct 26 ms 47388 KB Ok
30 Correct 27 ms 47396 KB Ok
31 Correct 26 ms 47492 KB Ok
32 Correct 26 ms 47432 KB Ok
33 Correct 25 ms 47428 KB Ok
34 Correct 29 ms 47692 KB Ok
35 Correct 28 ms 47728 KB Ok
36 Correct 30 ms 47820 KB Ok
37 Correct 30 ms 47748 KB Ok
38 Correct 28 ms 47692 KB Ok
39 Correct 28 ms 47708 KB Ok
40 Correct 31 ms 47672 KB Ok
41 Correct 29 ms 47680 KB Ok
42 Correct 31 ms 47692 KB Ok
43 Correct 30 ms 47668 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47232 KB Ok
2 Correct 24 ms 47304 KB Ok
3 Correct 23 ms 47212 KB Ok
4 Correct 24 ms 47292 KB Ok
5 Correct 22 ms 47272 KB Ok
6 Correct 24 ms 47288 KB Ok
7 Correct 23 ms 47252 KB Ok
8 Correct 24 ms 47204 KB Ok
9 Correct 24 ms 47196 KB Ok
10 Correct 23 ms 47180 KB Ok
11 Correct 24 ms 47240 KB Ok
12 Correct 28 ms 47180 KB Ok
13 Correct 22 ms 47220 KB Ok
14 Correct 25 ms 47268 KB Ok
15 Correct 22 ms 47260 KB Ok
16 Correct 23 ms 47180 KB Ok
17 Correct 24 ms 47288 KB Ok
18 Correct 25 ms 47448 KB Ok
19 Correct 36 ms 48324 KB Ok
20 Correct 29 ms 47752 KB Ok
21 Correct 40 ms 48412 KB Ok
22 Correct 32 ms 47944 KB Ok
23 Correct 23 ms 47180 KB Ok
24 Correct 26 ms 47180 KB Ok
25 Correct 23 ms 47280 KB Ok
26 Correct 24 ms 47284 KB Ok
27 Correct 28 ms 47196 KB Ok
28 Correct 23 ms 47180 KB Ok
29 Correct 24 ms 47216 KB Ok
30 Correct 25 ms 47220 KB Ok
31 Correct 25 ms 47180 KB Ok
32 Correct 25 ms 47240 KB Ok
33 Correct 24 ms 47308 KB Ok
34 Correct 25 ms 47416 KB Ok
35 Correct 26 ms 47512 KB Ok
36 Correct 25 ms 47424 KB Ok
37 Correct 26 ms 47488 KB Ok
38 Correct 29 ms 47368 KB Ok
39 Correct 26 ms 47388 KB Ok
40 Correct 27 ms 47396 KB Ok
41 Correct 26 ms 47492 KB Ok
42 Correct 26 ms 47432 KB Ok
43 Correct 25 ms 47428 KB Ok
44 Correct 29 ms 47692 KB Ok
45 Correct 28 ms 47728 KB Ok
46 Correct 30 ms 47820 KB Ok
47 Correct 30 ms 47748 KB Ok
48 Correct 28 ms 47692 KB Ok
49 Correct 28 ms 47708 KB Ok
50 Correct 31 ms 47672 KB Ok
51 Correct 29 ms 47680 KB Ok
52 Correct 31 ms 47692 KB Ok
53 Correct 30 ms 47668 KB Ok
54 Correct 112 ms 53420 KB Ok
55 Correct 134 ms 53828 KB Ok
56 Correct 123 ms 53836 KB Ok
57 Correct 100 ms 52684 KB Ok
58 Correct 122 ms 53696 KB Ok
59 Correct 123 ms 53304 KB Ok
60 Correct 102 ms 52756 KB Ok
61 Correct 101 ms 53188 KB Ok
62 Correct 147 ms 54056 KB Ok
63 Correct 112 ms 53112 KB Ok
64 Correct 131 ms 53824 KB Ok
65 Correct 121 ms 53664 KB Ok
66 Correct 117 ms 53332 KB Ok
67 Correct 98 ms 52932 KB Ok
68 Correct 126 ms 53644 KB Ok
69 Correct 250 ms 62392 KB Ok
70 Correct 261 ms 62340 KB Ok
71 Correct 230 ms 60212 KB Ok
72 Correct 239 ms 62444 KB Ok
73 Correct 274 ms 60620 KB Ok
74 Correct 266 ms 61608 KB Ok
75 Correct 220 ms 62068 KB Ok
76 Correct 231 ms 62288 KB Ok
77 Correct 229 ms 61116 KB Ok
78 Correct 239 ms 62344 KB Ok
79 Correct 253 ms 61620 KB Ok
80 Correct 238 ms 60476 KB Ok
81 Correct 246 ms 62348 KB Ok
82 Correct 226 ms 61476 KB Ok
83 Correct 229 ms 62396 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47232 KB Ok
2 Correct 24 ms 47304 KB Ok
3 Correct 23 ms 47212 KB Ok
4 Correct 24 ms 47292 KB Ok
5 Correct 22 ms 47272 KB Ok
6 Correct 24 ms 47288 KB Ok
7 Correct 23 ms 47252 KB Ok
8 Correct 24 ms 47204 KB Ok
9 Correct 24 ms 47196 KB Ok
10 Correct 23 ms 47180 KB Ok
11 Correct 24 ms 47240 KB Ok
12 Correct 28 ms 47180 KB Ok
13 Correct 22 ms 47220 KB Ok
14 Correct 25 ms 47268 KB Ok
15 Correct 22 ms 47260 KB Ok
16 Correct 23 ms 47180 KB Ok
17 Correct 24 ms 47288 KB Ok
18 Correct 25 ms 47448 KB Ok
19 Correct 36 ms 48324 KB Ok
20 Correct 29 ms 47752 KB Ok
21 Correct 40 ms 48412 KB Ok
22 Correct 32 ms 47944 KB Ok
23 Correct 23 ms 47180 KB Ok
24 Correct 26 ms 47180 KB Ok
25 Correct 23 ms 47280 KB Ok
26 Correct 24 ms 47284 KB Ok
27 Correct 28 ms 47196 KB Ok
28 Correct 23 ms 47180 KB Ok
29 Correct 24 ms 47216 KB Ok
30 Correct 25 ms 47220 KB Ok
31 Correct 25 ms 47180 KB Ok
32 Correct 25 ms 47240 KB Ok
33 Correct 24 ms 47308 KB Ok
34 Correct 25 ms 47180 KB Ok
35 Correct 24 ms 47264 KB Ok
36 Correct 24 ms 47296 KB Ok
37 Correct 27 ms 47280 KB Ok
38 Correct 24 ms 47288 KB Ok
39 Correct 127 ms 65348 KB Ok
40 Correct 111 ms 64908 KB Ok
41 Correct 188 ms 68216 KB Ok
42 Correct 161 ms 64312 KB Ok
43 Correct 100 ms 59500 KB Ok
44 Correct 157 ms 70124 KB Ok
45 Correct 25 ms 47416 KB Ok
46 Correct 26 ms 47512 KB Ok
47 Correct 25 ms 47424 KB Ok
48 Correct 26 ms 47488 KB Ok
49 Correct 29 ms 47368 KB Ok
50 Correct 26 ms 47388 KB Ok
51 Correct 27 ms 47396 KB Ok
52 Correct 26 ms 47492 KB Ok
53 Correct 26 ms 47432 KB Ok
54 Correct 25 ms 47428 KB Ok
55 Correct 29 ms 47692 KB Ok
56 Correct 28 ms 47728 KB Ok
57 Correct 30 ms 47820 KB Ok
58 Correct 30 ms 47748 KB Ok
59 Correct 28 ms 47692 KB Ok
60 Correct 28 ms 47708 KB Ok
61 Correct 31 ms 47672 KB Ok
62 Correct 29 ms 47680 KB Ok
63 Correct 31 ms 47692 KB Ok
64 Correct 30 ms 47668 KB Ok
65 Correct 112 ms 53420 KB Ok
66 Correct 134 ms 53828 KB Ok
67 Correct 123 ms 53836 KB Ok
68 Correct 100 ms 52684 KB Ok
69 Correct 122 ms 53696 KB Ok
70 Correct 123 ms 53304 KB Ok
71 Correct 102 ms 52756 KB Ok
72 Correct 101 ms 53188 KB Ok
73 Correct 147 ms 54056 KB Ok
74 Correct 112 ms 53112 KB Ok
75 Correct 131 ms 53824 KB Ok
76 Correct 121 ms 53664 KB Ok
77 Correct 117 ms 53332 KB Ok
78 Correct 98 ms 52932 KB Ok
79 Correct 126 ms 53644 KB Ok
80 Correct 250 ms 62392 KB Ok
81 Correct 261 ms 62340 KB Ok
82 Correct 230 ms 60212 KB Ok
83 Correct 239 ms 62444 KB Ok
84 Correct 274 ms 60620 KB Ok
85 Correct 266 ms 61608 KB Ok
86 Correct 220 ms 62068 KB Ok
87 Correct 231 ms 62288 KB Ok
88 Correct 229 ms 61116 KB Ok
89 Correct 239 ms 62344 KB Ok
90 Correct 253 ms 61620 KB Ok
91 Correct 238 ms 60476 KB Ok
92 Correct 246 ms 62348 KB Ok
93 Correct 226 ms 61476 KB Ok
94 Correct 229 ms 62396 KB Ok
95 Correct 258 ms 63520 KB Ok
96 Correct 386 ms 71348 KB Ok
97 Correct 361 ms 67388 KB Ok
98 Correct 274 ms 66864 KB Ok
99 Correct 291 ms 66372 KB Ok
100 Correct 337 ms 66892 KB Ok
101 Correct 322 ms 69036 KB Ok
102 Correct 345 ms 67276 KB Ok
103 Correct 336 ms 68656 KB Ok
104 Correct 373 ms 70148 KB Ok
105 Correct 406 ms 70988 KB Ok
106 Correct 306 ms 69984 KB Ok
107 Correct 360 ms 69752 KB Ok
108 Correct 398 ms 71144 KB Ok
109 Correct 327 ms 71516 KB Ok
110 Correct 1264 ms 109600 KB Ok
111 Correct 1449 ms 110264 KB Ok
112 Correct 1449 ms 103636 KB Ok
113 Correct 1234 ms 109372 KB Ok
114 Correct 1360 ms 102392 KB Ok
115 Correct 1562 ms 110176 KB Ok
116 Correct 1533 ms 109100 KB Ok
117 Correct 1320 ms 110308 KB Ok
118 Correct 1424 ms 100988 KB Ok
119 Correct 1428 ms 109348 KB Ok
120 Correct 1381 ms 110212 KB Ok
121 Correct 1334 ms 107012 KB Ok
122 Correct 1350 ms 109872 KB Ok
123 Correct 1456 ms 107084 KB Ok
124 Correct 1269 ms 102864 KB Ok
125 Correct 560 ms 93816 KB Ok