oj.uz

Submission #1114295

# Submission time Handle Problem Language Result Execution time Memory
1114295 2024-11-18T13:39:22 Z dosts Nice sequence (IZhO18_sequence) C++17
100 / 100
 821 ms 108784 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 29 ms 56400 KB Ok
2 Correct 30 ms 56448 KB Ok
3 Correct 30 ms 56400 KB Ok
4 Correct 30 ms 56380 KB Ok
5 Correct 28 ms 56392 KB Ok
6 Correct 32 ms 56392 KB Ok
7 Correct 31 ms 56400 KB Ok
8 Correct 31 ms 56400 KB Ok
9 Correct 32 ms 56616 KB Ok
10 Correct 30 ms 56400 KB Ok
11 Correct 30 ms 56400 KB Ok
12 Correct 34 ms 56400 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 56400 KB Ok
2 Correct 30 ms 56460 KB Ok
3 Correct 31 ms 56416 KB Ok
4 Correct 31 ms 56396 KB Ok
5 Correct 34 ms 56404 KB Ok
6 Correct 42 ms 56648 KB Ok
7 Correct 41 ms 57152 KB Ok
8 Correct 34 ms 56912 KB Ok
9 Correct 36 ms 57416 KB Ok
10 Correct 40 ms 56912 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 56392 KB Ok
2 Correct 29 ms 56428 KB Ok
3 Correct 29 ms 56520 KB Ok
4 Correct 28 ms 56400 KB Ok
5 Correct 33 ms 56556 KB Ok
6 Correct 29 ms 56344 KB Ok
7 Correct 30 ms 56400 KB Ok
8 Correct 32 ms 56400 KB Ok
9 Correct 32 ms 56404 KB Ok
10 Correct 33 ms 56400 KB Ok
11 Correct 38 ms 56516 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 56400 KB Ok
2 Correct 34 ms 56320 KB Ok
3 Correct 37 ms 56516 KB Ok
4 Correct 31 ms 56392 KB Ok
5 Correct 36 ms 56380 KB Ok
6 Correct 97 ms 67144 KB Ok
7 Correct 93 ms 71152 KB Ok
8 Correct 132 ms 74056 KB Ok
9 Correct 111 ms 71848 KB Ok
10 Correct 71 ms 64328 KB Ok
11 Correct 97 ms 69192 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 56400 KB Ok
2 Correct 30 ms 56448 KB Ok
3 Correct 30 ms 56400 KB Ok
4 Correct 30 ms 56380 KB Ok
5 Correct 28 ms 56392 KB Ok
6 Correct 32 ms 56392 KB Ok
7 Correct 31 ms 56400 KB Ok
8 Correct 31 ms 56400 KB Ok
9 Correct 32 ms 56616 KB Ok
10 Correct 30 ms 56400 KB Ok
11 Correct 30 ms 56400 KB Ok
12 Correct 34 ms 56400 KB Ok
13 Correct 35 ms 56392 KB Ok
14 Correct 29 ms 56428 KB Ok
15 Correct 29 ms 56520 KB Ok
16 Correct 28 ms 56400 KB Ok
17 Correct 33 ms 56556 KB Ok
18 Correct 29 ms 56344 KB Ok
19 Correct 30 ms 56400 KB Ok
20 Correct 32 ms 56400 KB Ok
21 Correct 32 ms 56404 KB Ok
22 Correct 33 ms 56400 KB Ok
23 Correct 38 ms 56516 KB Ok
24 Correct 35 ms 56452 KB Ok
25 Correct 35 ms 56656 KB Ok
26 Correct 31 ms 56540 KB Ok
27 Correct 31 ms 56672 KB Ok
28 Correct 30 ms 56656 KB Ok
29 Correct 33 ms 56420 KB Ok
30 Correct 40 ms 56664 KB Ok
31 Correct 32 ms 56656 KB Ok
32 Correct 34 ms 56648 KB Ok
33 Correct 31 ms 56448 KB Ok
34 Correct 32 ms 56784 KB Ok
35 Correct 33 ms 56904 KB Ok
36 Correct 32 ms 56912 KB Ok
37 Correct 32 ms 56712 KB Ok
38 Correct 38 ms 56928 KB Ok
39 Correct 32 ms 56656 KB Ok
40 Correct 30 ms 56832 KB Ok
41 Correct 35 ms 56912 KB Ok
42 Correct 37 ms 56796 KB Ok
43 Correct 35 ms 56852 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 56400 KB Ok
2 Correct 30 ms 56448 KB Ok
3 Correct 30 ms 56400 KB Ok
4 Correct 30 ms 56380 KB Ok
5 Correct 28 ms 56392 KB Ok
6 Correct 32 ms 56392 KB Ok
7 Correct 31 ms 56400 KB Ok
8 Correct 31 ms 56400 KB Ok
9 Correct 32 ms 56616 KB Ok
10 Correct 30 ms 56400 KB Ok
11 Correct 30 ms 56400 KB Ok
12 Correct 34 ms 56400 KB Ok
13 Correct 31 ms 56400 KB Ok
14 Correct 30 ms 56460 KB Ok
15 Correct 31 ms 56416 KB Ok
16 Correct 31 ms 56396 KB Ok
17 Correct 34 ms 56404 KB Ok
18 Correct 42 ms 56648 KB Ok
19 Correct 41 ms 57152 KB Ok
20 Correct 34 ms 56912 KB Ok
21 Correct 36 ms 57416 KB Ok
22 Correct 40 ms 56912 KB Ok
23 Correct 35 ms 56392 KB Ok
24 Correct 29 ms 56428 KB Ok
25 Correct 29 ms 56520 KB Ok
26 Correct 28 ms 56400 KB Ok
27 Correct 33 ms 56556 KB Ok
28 Correct 29 ms 56344 KB Ok
29 Correct 30 ms 56400 KB Ok
30 Correct 32 ms 56400 KB Ok
31 Correct 32 ms 56404 KB Ok
32 Correct 33 ms 56400 KB Ok
33 Correct 38 ms 56516 KB Ok
34 Correct 35 ms 56452 KB Ok
35 Correct 35 ms 56656 KB Ok
36 Correct 31 ms 56540 KB Ok
37 Correct 31 ms 56672 KB Ok
38 Correct 30 ms 56656 KB Ok
39 Correct 33 ms 56420 KB Ok
40 Correct 40 ms 56664 KB Ok
41 Correct 32 ms 56656 KB Ok
42 Correct 34 ms 56648 KB Ok
43 Correct 31 ms 56448 KB Ok
44 Correct 32 ms 56784 KB Ok
45 Correct 33 ms 56904 KB Ok
46 Correct 32 ms 56912 KB Ok
47 Correct 32 ms 56712 KB Ok
48 Correct 38 ms 56928 KB Ok
49 Correct 32 ms 56656 KB Ok
50 Correct 30 ms 56832 KB Ok
51 Correct 35 ms 56912 KB Ok
52 Correct 37 ms 56796 KB Ok
53 Correct 35 ms 56852 KB Ok
54 Correct 78 ms 61012 KB Ok
55 Correct 76 ms 61460 KB Ok
56 Correct 78 ms 61372 KB Ok
57 Correct 64 ms 60544 KB Ok
58 Correct 76 ms 60748 KB Ok
59 Correct 73 ms 60488 KB Ok
60 Correct 80 ms 60208 KB Ok
61 Correct 66 ms 60748 KB Ok
62 Correct 88 ms 61256 KB Ok
63 Correct 69 ms 60692 KB Ok
64 Correct 84 ms 61276 KB Ok
65 Correct 82 ms 61000 KB Ok
66 Correct 78 ms 60744 KB Ok
67 Correct 69 ms 60636 KB Ok
68 Correct 74 ms 61000 KB Ok
69 Correct 155 ms 68680 KB Ok
70 Correct 134 ms 69192 KB Ok
71 Correct 153 ms 68728 KB Ok
72 Correct 149 ms 68680 KB Ok
73 Correct 120 ms 68168 KB Ok
74 Correct 127 ms 67976 KB Ok
75 Correct 139 ms 67912 KB Ok
76 Correct 140 ms 68952 KB Ok
77 Correct 137 ms 67656 KB Ok
78 Correct 124 ms 68084 KB Ok
79 Correct 121 ms 68680 KB Ok
80 Correct 136 ms 68768 KB Ok
81 Correct 153 ms 68168 KB Ok
82 Correct 148 ms 68792 KB Ok
83 Correct 131 ms 67912 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 56400 KB Ok
2 Correct 30 ms 56448 KB Ok
3 Correct 30 ms 56400 KB Ok
4 Correct 30 ms 56380 KB Ok
5 Correct 28 ms 56392 KB Ok
6 Correct 32 ms 56392 KB Ok
7 Correct 31 ms 56400 KB Ok
8 Correct 31 ms 56400 KB Ok
9 Correct 32 ms 56616 KB Ok
10 Correct 30 ms 56400 KB Ok
11 Correct 30 ms 56400 KB Ok
12 Correct 34 ms 56400 KB Ok
13 Correct 31 ms 56400 KB Ok
14 Correct 30 ms 56460 KB Ok
15 Correct 31 ms 56416 KB Ok
16 Correct 31 ms 56396 KB Ok
17 Correct 34 ms 56404 KB Ok
18 Correct 42 ms 56648 KB Ok
19 Correct 41 ms 57152 KB Ok
20 Correct 34 ms 56912 KB Ok
21 Correct 36 ms 57416 KB Ok
22 Correct 40 ms 56912 KB Ok
23 Correct 35 ms 56392 KB Ok
24 Correct 29 ms 56428 KB Ok
25 Correct 29 ms 56520 KB Ok
26 Correct 28 ms 56400 KB Ok
27 Correct 33 ms 56556 KB Ok
28 Correct 29 ms 56344 KB Ok
29 Correct 30 ms 56400 KB Ok
30 Correct 32 ms 56400 KB Ok
31 Correct 32 ms 56404 KB Ok
32 Correct 33 ms 56400 KB Ok
33 Correct 38 ms 56516 KB Ok
34 Correct 41 ms 56400 KB Ok
35 Correct 34 ms 56320 KB Ok
36 Correct 37 ms 56516 KB Ok
37 Correct 31 ms 56392 KB Ok
38 Correct 36 ms 56380 KB Ok
39 Correct 97 ms 67144 KB Ok
40 Correct 93 ms 71152 KB Ok
41 Correct 132 ms 74056 KB Ok
42 Correct 111 ms 71848 KB Ok
43 Correct 71 ms 64328 KB Ok
44 Correct 97 ms 69192 KB Ok
45 Correct 35 ms 56452 KB Ok
46 Correct 35 ms 56656 KB Ok
47 Correct 31 ms 56540 KB Ok
48 Correct 31 ms 56672 KB Ok
49 Correct 30 ms 56656 KB Ok
50 Correct 33 ms 56420 KB Ok
51 Correct 40 ms 56664 KB Ok
52 Correct 32 ms 56656 KB Ok
53 Correct 34 ms 56648 KB Ok
54 Correct 31 ms 56448 KB Ok
55 Correct 32 ms 56784 KB Ok
56 Correct 33 ms 56904 KB Ok
57 Correct 32 ms 56912 KB Ok
58 Correct 32 ms 56712 KB Ok
59 Correct 38 ms 56928 KB Ok
60 Correct 32 ms 56656 KB Ok
61 Correct 30 ms 56832 KB Ok
62 Correct 35 ms 56912 KB Ok
63 Correct 37 ms 56796 KB Ok
64 Correct 35 ms 56852 KB Ok
65 Correct 78 ms 61012 KB Ok
66 Correct 76 ms 61460 KB Ok
67 Correct 78 ms 61372 KB Ok
68 Correct 64 ms 60544 KB Ok
69 Correct 76 ms 60748 KB Ok
70 Correct 73 ms 60488 KB Ok
71 Correct 80 ms 60208 KB Ok
72 Correct 66 ms 60748 KB Ok
73 Correct 88 ms 61256 KB Ok
74 Correct 69 ms 60692 KB Ok
75 Correct 84 ms 61276 KB Ok
76 Correct 82 ms 61000 KB Ok
77 Correct 78 ms 60744 KB Ok
78 Correct 69 ms 60636 KB Ok
79 Correct 74 ms 61000 KB Ok
80 Correct 155 ms 68680 KB Ok
81 Correct 134 ms 69192 KB Ok
82 Correct 153 ms 68728 KB Ok
83 Correct 149 ms 68680 KB Ok
84 Correct 120 ms 68168 KB Ok
85 Correct 127 ms 67976 KB Ok
86 Correct 139 ms 67912 KB Ok
87 Correct 140 ms 68952 KB Ok
88 Correct 137 ms 67656 KB Ok
89 Correct 124 ms 68084 KB Ok
90 Correct 121 ms 68680 KB Ok
91 Correct 136 ms 68768 KB Ok
92 Correct 153 ms 68168 KB Ok
93 Correct 148 ms 68792 KB Ok
94 Correct 131 ms 67912 KB Ok
95 Correct 125 ms 68432 KB Ok
96 Correct 183 ms 73544 KB Ok
97 Correct 165 ms 70504 KB Ok
98 Correct 136 ms 70320 KB Ok
99 Correct 154 ms 70108 KB Ok
100 Correct 180 ms 69960 KB Ok
101 Correct 170 ms 73920 KB Ok
102 Correct 165 ms 70728 KB Ok
103 Correct 165 ms 71496 KB Ok
104 Correct 207 ms 73032 KB Ok
105 Correct 217 ms 73288 KB Ok
106 Correct 175 ms 73544 KB Ok
107 Correct 181 ms 72520 KB Ok
108 Correct 241 ms 73284 KB Ok
109 Correct 185 ms 74052 KB Ok
110 Correct 604 ms 106056 KB Ok
111 Correct 589 ms 108256 KB Ok
112 Correct 567 ms 105800 KB Ok
113 Correct 551 ms 108496 KB Ok
114 Correct 752 ms 108784 KB Ok
115 Correct 753 ms 106312 KB Ok
116 Correct 821 ms 108472 KB Ok
117 Correct 586 ms 107544 KB Ok
118 Correct 581 ms 107936 KB Ok
119 Correct 541 ms 107080 KB Ok
120 Correct 490 ms 107080 KB Ok
121 Correct 625 ms 106576 KB Ok
122 Correct 640 ms 107080 KB Ok
123 Correct 625 ms 108504 KB Ok
124 Correct 521 ms 103496 KB Ok
125 Correct 274 ms 91976 KB Ok