oj.uz

Submission #1114293

# Submission time Handle Problem Language Result Execution time Memory
1114293 2024-11-18T13:37:57 Z vjudge1 Nice sequence (IZhO18_sequence) C++17
100 / 100
 804 ms 110672 KB 
//Dost SEFEROĞLU
#include <bits/stdc++.h>
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e18;
const int N = 2e5+50,Q = 2e5+50;
const int LIM = 2000001;
vi edges[LIM];
bool vis[LIM],act[LIM];
int v[LIM];
struct DAG {
    int nd;
    bool cyclic = 0;
    void addedge(int a,int b) {
        edges[a].push_back(b);
    }
    void reset() {
        cyclic = 0;;
        for (int i = 0;i<=nd;i++) edges[i].clear(),vis[i] = 0,act[i] = 0;
    }
    void cyclecheck(int node) {
        if (vis[node]) return;
        if (cyclic) return;
        vis[node] = act[node] = 1;
        for (auto it : edges[node]) {
            if (act[it]) {
                cyclic = 1;
                return;
            }
            else if (!vis[it]) cyclecheck(it);
        }
        act[node] = 0;
    }
    void checkcycle() {
        for (int i = 0;i<=nd;i++) {
            cyclecheck(i);
            if (cyclic) break;
        }
    }
    int mex = 1;
    int dfs(int node) {
        if (vis[node]) return v[node];
        vis[node] = 1;
        for (auto it : edges[node]) dfs(it);
        return v[node] = mex++;
    }
    void solve() {
        for (int i = 0;i<=nd;i++) vis[i] = 0;
        for (int i = 0;i<=nd;i++) dfs(i);
    }
};
void solve() { 
    int n,m;
    cin >> n >> m;
    DAG D;
    int r = n+m-__gcd(n,m)-1;
    memset(v,-1,sizeof v);
    for (int i=0;i<=r;i++) edges[i].clear();
    cout << r << '\n';
    D.nd = r;
    for (int i = 1;i<=r;i++) {
        if (i >= m) D.addedge(i,i-m);
        if (i >= n) D.addedge(i-n,i);
    } 
    D.solve();
    for (int i = 1;i<=r;i++) {
        assert(v[i] != v[i-1]);
        cout << v[i]-v[i-1] << ' ';
    }
    cout << '\n'; 
}                    
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    cin >> t; 
    while (t --> 0) solve();
}

Compilation message

sequence.cpp:12:29: warning: overflow in conversion from 'double' to 'int' changes value from '2.0e+18' to '2147483647' [-Woverflow]
   12 | const int MOD = 1e9+7,inf = 2e18;
      |                             ^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 56400 KB Ok
2 Correct 33 ms 56328 KB Ok
3 Correct 34 ms 56392 KB Ok
4 Correct 33 ms 56400 KB Ok
5 Correct 34 ms 56400 KB Ok
6 Correct 34 ms 56332 KB Ok
7 Correct 33 ms 56468 KB Ok
8 Correct 39 ms 56404 KB Ok
9 Correct 33 ms 56388 KB Ok
10 Correct 33 ms 56392 KB Ok
11 Correct 36 ms 56392 KB Ok
12 Correct 33 ms 56404 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 56400 KB Ok
2 Correct 34 ms 56392 KB Ok
3 Correct 34 ms 56516 KB Ok
4 Correct 34 ms 56396 KB Ok
5 Correct 35 ms 56480 KB Ok
6 Correct 35 ms 56464 KB Ok
7 Correct 38 ms 57296 KB Ok
8 Correct 37 ms 56912 KB Ok
9 Correct 42 ms 57596 KB Ok
10 Correct 44 ms 56908 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 56420 KB Ok
2 Correct 37 ms 56400 KB Ok
3 Correct 38 ms 56404 KB Ok
4 Correct 38 ms 56440 KB Ok
5 Correct 37 ms 56404 KB Ok
6 Correct 34 ms 56480 KB Ok
7 Correct 36 ms 56540 KB Ok
8 Correct 36 ms 56392 KB Ok
9 Correct 38 ms 56400 KB Ok
10 Correct 35 ms 56392 KB Ok
11 Correct 37 ms 56376 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 56400 KB Ok
2 Correct 42 ms 56400 KB Ok
3 Correct 36 ms 56400 KB Ok
4 Correct 40 ms 56400 KB Ok
5 Correct 36 ms 56404 KB Ok
6 Correct 94 ms 67132 KB Ok
7 Correct 100 ms 71140 KB Ok
8 Correct 130 ms 74056 KB Ok
9 Correct 114 ms 71752 KB Ok
10 Correct 72 ms 64328 KB Ok
11 Correct 115 ms 69320 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 56400 KB Ok
2 Correct 33 ms 56328 KB Ok
3 Correct 34 ms 56392 KB Ok
4 Correct 33 ms 56400 KB Ok
5 Correct 34 ms 56400 KB Ok
6 Correct 34 ms 56332 KB Ok
7 Correct 33 ms 56468 KB Ok
8 Correct 39 ms 56404 KB Ok
9 Correct 33 ms 56388 KB Ok
10 Correct 33 ms 56392 KB Ok
11 Correct 36 ms 56392 KB Ok
12 Correct 33 ms 56404 KB Ok
13 Correct 35 ms 56420 KB Ok
14 Correct 37 ms 56400 KB Ok
15 Correct 38 ms 56404 KB Ok
16 Correct 38 ms 56440 KB Ok
17 Correct 37 ms 56404 KB Ok
18 Correct 34 ms 56480 KB Ok
19 Correct 36 ms 56540 KB Ok
20 Correct 36 ms 56392 KB Ok
21 Correct 38 ms 56400 KB Ok
22 Correct 35 ms 56392 KB Ok
23 Correct 37 ms 56376 KB Ok
24 Correct 36 ms 56648 KB Ok
25 Correct 38 ms 56552 KB Ok
26 Correct 37 ms 56648 KB Ok
27 Correct 36 ms 56648 KB Ok
28 Correct 38 ms 56648 KB Ok
29 Correct 39 ms 56648 KB Ok
30 Correct 37 ms 56656 KB Ok
31 Correct 39 ms 56648 KB Ok
32 Correct 38 ms 56696 KB Ok
33 Correct 38 ms 56568 KB Ok
34 Correct 42 ms 56648 KB Ok
35 Correct 40 ms 56736 KB Ok
36 Correct 40 ms 56912 KB Ok
37 Correct 43 ms 56912 KB Ok
38 Correct 41 ms 56904 KB Ok
39 Correct 39 ms 56692 KB Ok
40 Correct 39 ms 56780 KB Ok
41 Correct 39 ms 56760 KB Ok
42 Correct 38 ms 56776 KB Ok
43 Correct 40 ms 56904 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 56400 KB Ok
2 Correct 33 ms 56328 KB Ok
3 Correct 34 ms 56392 KB Ok
4 Correct 33 ms 56400 KB Ok
5 Correct 34 ms 56400 KB Ok
6 Correct 34 ms 56332 KB Ok
7 Correct 33 ms 56468 KB Ok
8 Correct 39 ms 56404 KB Ok
9 Correct 33 ms 56388 KB Ok
10 Correct 33 ms 56392 KB Ok
11 Correct 36 ms 56392 KB Ok
12 Correct 33 ms 56404 KB Ok
13 Correct 33 ms 56400 KB Ok
14 Correct 34 ms 56392 KB Ok
15 Correct 34 ms 56516 KB Ok
16 Correct 34 ms 56396 KB Ok
17 Correct 35 ms 56480 KB Ok
18 Correct 35 ms 56464 KB Ok
19 Correct 38 ms 57296 KB Ok
20 Correct 37 ms 56912 KB Ok
21 Correct 42 ms 57596 KB Ok
22 Correct 44 ms 56908 KB Ok
23 Correct 35 ms 56420 KB Ok
24 Correct 37 ms 56400 KB Ok
25 Correct 38 ms 56404 KB Ok
26 Correct 38 ms 56440 KB Ok
27 Correct 37 ms 56404 KB Ok
28 Correct 34 ms 56480 KB Ok
29 Correct 36 ms 56540 KB Ok
30 Correct 36 ms 56392 KB Ok
31 Correct 38 ms 56400 KB Ok
32 Correct 35 ms 56392 KB Ok
33 Correct 37 ms 56376 KB Ok
34 Correct 36 ms 56648 KB Ok
35 Correct 38 ms 56552 KB Ok
36 Correct 37 ms 56648 KB Ok
37 Correct 36 ms 56648 KB Ok
38 Correct 38 ms 56648 KB Ok
39 Correct 39 ms 56648 KB Ok
40 Correct 37 ms 56656 KB Ok
41 Correct 39 ms 56648 KB Ok
42 Correct 38 ms 56696 KB Ok
43 Correct 38 ms 56568 KB Ok
44 Correct 42 ms 56648 KB Ok
45 Correct 40 ms 56736 KB Ok
46 Correct 40 ms 56912 KB Ok
47 Correct 43 ms 56912 KB Ok
48 Correct 41 ms 56904 KB Ok
49 Correct 39 ms 56692 KB Ok
50 Correct 39 ms 56780 KB Ok
51 Correct 39 ms 56760 KB Ok
52 Correct 38 ms 56776 KB Ok
53 Correct 40 ms 56904 KB Ok
54 Correct 91 ms 63064 KB Ok
55 Correct 78 ms 61540 KB Ok
56 Correct 78 ms 61512 KB Ok
57 Correct 65 ms 60416 KB Ok
58 Correct 78 ms 60744 KB Ok
59 Correct 69 ms 60488 KB Ok
60 Correct 65 ms 60232 KB Ok
61 Correct 66 ms 60628 KB Ok
62 Correct 76 ms 61256 KB Ok
63 Correct 68 ms 60488 KB Ok
64 Correct 76 ms 61500 KB Ok
65 Correct 74 ms 61000 KB Ok
66 Correct 70 ms 60744 KB Ok
67 Correct 75 ms 60600 KB Ok
68 Correct 77 ms 61000 KB Ok
69 Correct 163 ms 68592 KB Ok
70 Correct 134 ms 69192 KB Ok
71 Correct 146 ms 68680 KB Ok
72 Correct 141 ms 68728 KB Ok
73 Correct 127 ms 68260 KB Ok
74 Correct 137 ms 67912 KB Ok
75 Correct 138 ms 68036 KB Ok
76 Correct 133 ms 68936 KB Ok
77 Correct 134 ms 67560 KB Ok
78 Correct 130 ms 67912 KB Ok
79 Correct 125 ms 68612 KB Ok
80 Correct 138 ms 68684 KB Ok
81 Correct 146 ms 68184 KB Ok
82 Correct 139 ms 68592 KB Ok
83 Correct 132 ms 67916 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 56400 KB Ok
2 Correct 33 ms 56328 KB Ok
3 Correct 34 ms 56392 KB Ok
4 Correct 33 ms 56400 KB Ok
5 Correct 34 ms 56400 KB Ok
6 Correct 34 ms 56332 KB Ok
7 Correct 33 ms 56468 KB Ok
8 Correct 39 ms 56404 KB Ok
9 Correct 33 ms 56388 KB Ok
10 Correct 33 ms 56392 KB Ok
11 Correct 36 ms 56392 KB Ok
12 Correct 33 ms 56404 KB Ok
13 Correct 33 ms 56400 KB Ok
14 Correct 34 ms 56392 KB Ok
15 Correct 34 ms 56516 KB Ok
16 Correct 34 ms 56396 KB Ok
17 Correct 35 ms 56480 KB Ok
18 Correct 35 ms 56464 KB Ok
19 Correct 38 ms 57296 KB Ok
20 Correct 37 ms 56912 KB Ok
21 Correct 42 ms 57596 KB Ok
22 Correct 44 ms 56908 KB Ok
23 Correct 35 ms 56420 KB Ok
24 Correct 37 ms 56400 KB Ok
25 Correct 38 ms 56404 KB Ok
26 Correct 38 ms 56440 KB Ok
27 Correct 37 ms 56404 KB Ok
28 Correct 34 ms 56480 KB Ok
29 Correct 36 ms 56540 KB Ok
30 Correct 36 ms 56392 KB Ok
31 Correct 38 ms 56400 KB Ok
32 Correct 35 ms 56392 KB Ok
33 Correct 37 ms 56376 KB Ok
34 Correct 36 ms 56400 KB Ok
35 Correct 42 ms 56400 KB Ok
36 Correct 36 ms 56400 KB Ok
37 Correct 40 ms 56400 KB Ok
38 Correct 36 ms 56404 KB Ok
39 Correct 94 ms 67132 KB Ok
40 Correct 100 ms 71140 KB Ok
41 Correct 130 ms 74056 KB Ok
42 Correct 114 ms 71752 KB Ok
43 Correct 72 ms 64328 KB Ok
44 Correct 115 ms 69320 KB Ok
45 Correct 36 ms 56648 KB Ok
46 Correct 38 ms 56552 KB Ok
47 Correct 37 ms 56648 KB Ok
48 Correct 36 ms 56648 KB Ok
49 Correct 38 ms 56648 KB Ok
50 Correct 39 ms 56648 KB Ok
51 Correct 37 ms 56656 KB Ok
52 Correct 39 ms 56648 KB Ok
53 Correct 38 ms 56696 KB Ok
54 Correct 38 ms 56568 KB Ok
55 Correct 42 ms 56648 KB Ok
56 Correct 40 ms 56736 KB Ok
57 Correct 40 ms 56912 KB Ok
58 Correct 43 ms 56912 KB Ok
59 Correct 41 ms 56904 KB Ok
60 Correct 39 ms 56692 KB Ok
61 Correct 39 ms 56780 KB Ok
62 Correct 39 ms 56760 KB Ok
63 Correct 38 ms 56776 KB Ok
64 Correct 40 ms 56904 KB Ok
65 Correct 91 ms 63064 KB Ok
66 Correct 78 ms 61540 KB Ok
67 Correct 78 ms 61512 KB Ok
68 Correct 65 ms 60416 KB Ok
69 Correct 78 ms 60744 KB Ok
70 Correct 69 ms 60488 KB Ok
71 Correct 65 ms 60232 KB Ok
72 Correct 66 ms 60628 KB Ok
73 Correct 76 ms 61256 KB Ok
74 Correct 68 ms 60488 KB Ok
75 Correct 76 ms 61500 KB Ok
76 Correct 74 ms 61000 KB Ok
77 Correct 70 ms 60744 KB Ok
78 Correct 75 ms 60600 KB Ok
79 Correct 77 ms 61000 KB Ok
80 Correct 163 ms 68592 KB Ok
81 Correct 134 ms 69192 KB Ok
82 Correct 146 ms 68680 KB Ok
83 Correct 141 ms 68728 KB Ok
84 Correct 127 ms 68260 KB Ok
85 Correct 137 ms 67912 KB Ok
86 Correct 138 ms 68036 KB Ok
87 Correct 133 ms 68936 KB Ok
88 Correct 134 ms 67560 KB Ok
89 Correct 130 ms 67912 KB Ok
90 Correct 125 ms 68612 KB Ok
91 Correct 138 ms 68684 KB Ok
92 Correct 146 ms 68184 KB Ok
93 Correct 139 ms 68592 KB Ok
94 Correct 132 ms 67916 KB Ok
95 Correct 163 ms 68424 KB Ok
96 Correct 203 ms 73544 KB Ok
97 Correct 163 ms 70536 KB Ok
98 Correct 135 ms 70472 KB Ok
99 Correct 152 ms 70108 KB Ok
100 Correct 153 ms 69960 KB Ok
101 Correct 160 ms 72008 KB Ok
102 Correct 156 ms 70728 KB Ok
103 Correct 161 ms 71496 KB Ok
104 Correct 208 ms 73212 KB Ok
105 Correct 190 ms 73288 KB Ok
106 Correct 170 ms 73544 KB Ok
107 Correct 177 ms 72464 KB Ok
108 Correct 198 ms 73288 KB Ok
109 Correct 209 ms 74068 KB Ok
110 Correct 612 ms 106104 KB Ok
111 Correct 609 ms 110672 KB Ok
112 Correct 550 ms 105544 KB Ok
113 Correct 482 ms 108556 KB Ok
114 Correct 691 ms 108872 KB Ok
115 Correct 571 ms 106312 KB Ok
116 Correct 756 ms 108616 KB Ok
117 Correct 563 ms 107592 KB Ok
118 Correct 804 ms 108044 KB Ok
119 Correct 510 ms 107336 KB Ok
120 Correct 479 ms 107100 KB Ok
121 Correct 666 ms 106608 KB Ok
122 Correct 584 ms 107080 KB Ok
123 Correct 638 ms 108492 KB Ok
124 Correct 631 ms 103496 KB Ok
125 Correct 291 ms 91980 KB Ok