oj.uz

Submission #879435

# Submission time Handle Problem Language Result Execution time Memory
879435 2023-11-27T11:29:37 Z vjudge1 Nice sequence (IZhO18_sequence) C++17
100 / 100
 1046 ms 82580 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#pragma GCC optimize("Ofast","O3","unroll-loops")
#pragma GCC target("avx2")
const int N = 1e6 + 10, MOD = 998244353;
int timer = 1,pref[N],n,m,used[N];
vector<int> g[N],ord;
bool ok = 1;
void dfs(int v){
    used[v] = 1;
    for(int to:g[v]){
        if(used[to] == 1){
            ok = false;
        }
        if(!used[to]){
            dfs(to);
        }
    }
    used[v] = 2;
    ord.push_back(v);
}
bool can(int len){
  	assert(ok == 1);
    for(int i = 1;i <= len; i++){
        if(i - m >= 0){
            g[i - m].push_back(i);
        }
        if(i - n >= 0){
            g[i].push_back(i - n);
        }
    }
    for(int i = 0;i <= len;i++){
        if(!used[i]){
            dfs(i);
        }
    }
    reverse(ord.begin(),ord.end());
    for(auto i:ord){
        pref[i] = timer++;
    }
    timer = 1;
    ord.clear();
    for(int i = 0;i <= len;i++){
        g[i].clear();
    }
    for(int i = 0;i <= len;i++){
        used[i] = 0;
    }
  	bool ans = ok;
  	ok = 1;
    return ans;
}
void test(){
    cin >> n >> m;
    int l = n + m - gcd(n,m) - 1;
  	can(l);
    cout << l << '\n';
    for(int i = 1;i <= l;i++){
        cout << pref[i] - pref[i - 1] << ' ';
    }
    cout << '\n';
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        test();
    }
}

Subtask #1
6.0 / 6.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27228 KB Ok
2 Correct 6 ms 27228 KB Ok
3 Correct 6 ms 27228 KB Ok
4 Correct 8 ms 27228 KB Ok
5 Correct 6 ms 27228 KB Ok
6 Correct 9 ms 27720 KB Ok
7 Correct 13 ms 27992 KB Ok
8 Correct 9 ms 27480 KB Ok
9 Correct 13 ms 28252 KB Ok
10 Correct 9 ms 27740 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 27228 KB Ok
2 Correct 6 ms 27228 KB Ok
3 Correct 6 ms 27224 KB Ok
4 Correct 6 ms 27232 KB Ok
5 Correct 5 ms 27224 KB Ok
6 Correct 6 ms 27228 KB Ok
7 Correct 6 ms 27228 KB Ok
8 Correct 5 ms 27228 KB Ok
9 Correct 6 ms 27228 KB Ok
10 Correct 5 ms 27308 KB Ok
11 Correct 6 ms 27316 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27228 KB Ok
2 Correct 6 ms 27228 KB Ok
3 Correct 6 ms 27224 KB Ok
4 Correct 6 ms 27228 KB Ok
5 Correct 6 ms 27228 KB Ok
6 Correct 77 ms 41160 KB Ok
7 Correct 57 ms 40648 KB Ok
8 Correct 100 ms 43720 KB Ok
9 Correct 79 ms 41416 KB Ok
10 Correct 52 ms 36764 KB Ok
11 Correct 85 ms 44900 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27228 KB Ok
2 Correct 6 ms 27228 KB Ok
3 Correct 6 ms 27228 KB Ok
4 Correct 7 ms 27480 KB Ok
5 Correct 5 ms 27224 KB Ok
6 Correct 6 ms 27228 KB Ok
7 Correct 6 ms 27228 KB Ok
8 Correct 6 ms 27228 KB Ok
9 Correct 6 ms 27228 KB Ok
10 Correct 5 ms 27228 KB Ok
11 Correct 5 ms 27228 KB Ok
12 Correct 6 ms 27228 KB Ok
13 Correct 7 ms 27228 KB Ok
14 Correct 6 ms 27228 KB Ok
15 Correct 6 ms 27224 KB Ok
16 Correct 6 ms 27232 KB Ok
17 Correct 5 ms 27224 KB Ok
18 Correct 6 ms 27228 KB Ok
19 Correct 6 ms 27228 KB Ok
20 Correct 5 ms 27228 KB Ok
21 Correct 6 ms 27228 KB Ok
22 Correct 5 ms 27308 KB Ok
23 Correct 6 ms 27316 KB Ok
24 Correct 7 ms 27224 KB Ok
25 Correct 7 ms 27484 KB Ok
26 Correct 7 ms 27228 KB Ok
27 Correct 6 ms 27484 KB Ok
28 Correct 7 ms 27448 KB Ok
29 Correct 7 ms 27224 KB Ok
30 Correct 7 ms 27228 KB Ok
31 Correct 7 ms 27256 KB Ok
32 Correct 7 ms 27228 KB Ok
33 Correct 7 ms 27464 KB Ok
34 Correct 9 ms 27484 KB Ok
35 Correct 8 ms 27564 KB Ok
36 Correct 9 ms 27508 KB Ok
37 Correct 8 ms 27484 KB Ok
38 Correct 8 ms 27484 KB Ok
39 Correct 8 ms 27484 KB Ok
40 Correct 8 ms 27484 KB Ok
41 Correct 8 ms 27484 KB Ok
42 Correct 8 ms 27484 KB Ok
43 Correct 8 ms 27484 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27228 KB Ok
2 Correct 6 ms 27228 KB Ok
3 Correct 6 ms 27228 KB Ok
4 Correct 7 ms 27480 KB Ok
5 Correct 5 ms 27224 KB Ok
6 Correct 6 ms 27228 KB Ok
7 Correct 6 ms 27228 KB Ok
8 Correct 6 ms 27228 KB Ok
9 Correct 6 ms 27228 KB Ok
10 Correct 5 ms 27228 KB Ok
11 Correct 5 ms 27228 KB Ok
12 Correct 6 ms 27228 KB Ok
13 Correct 6 ms 27228 KB Ok
14 Correct 6 ms 27228 KB Ok
15 Correct 6 ms 27228 KB Ok
16 Correct 8 ms 27228 KB Ok
17 Correct 6 ms 27228 KB Ok
18 Correct 9 ms 27720 KB Ok
19 Correct 13 ms 27992 KB Ok
20 Correct 9 ms 27480 KB Ok
21 Correct 13 ms 28252 KB Ok
22 Correct 9 ms 27740 KB Ok
23 Correct 7 ms 27228 KB Ok
24 Correct 6 ms 27228 KB Ok
25 Correct 6 ms 27224 KB Ok
26 Correct 6 ms 27232 KB Ok
27 Correct 5 ms 27224 KB Ok
28 Correct 6 ms 27228 KB Ok
29 Correct 6 ms 27228 KB Ok
30 Correct 5 ms 27228 KB Ok
31 Correct 6 ms 27228 KB Ok
32 Correct 5 ms 27308 KB Ok
33 Correct 6 ms 27316 KB Ok
34 Correct 7 ms 27224 KB Ok
35 Correct 7 ms 27484 KB Ok
36 Correct 7 ms 27228 KB Ok
37 Correct 6 ms 27484 KB Ok
38 Correct 7 ms 27448 KB Ok
39 Correct 7 ms 27224 KB Ok
40 Correct 7 ms 27228 KB Ok
41 Correct 7 ms 27256 KB Ok
42 Correct 7 ms 27228 KB Ok
43 Correct 7 ms 27464 KB Ok
44 Correct 9 ms 27484 KB Ok
45 Correct 8 ms 27564 KB Ok
46 Correct 9 ms 27508 KB Ok
47 Correct 8 ms 27484 KB Ok
48 Correct 8 ms 27484 KB Ok
49 Correct 8 ms 27484 KB Ok
50 Correct 8 ms 27484 KB Ok
51 Correct 8 ms 27484 KB Ok
52 Correct 8 ms 27484 KB Ok
53 Correct 8 ms 27484 KB Ok
54 Correct 49 ms 32684 KB Ok
55 Correct 62 ms 33032 KB Ok
56 Correct 53 ms 32980 KB Ok
57 Correct 44 ms 31956 KB Ok
58 Correct 51 ms 32904 KB Ok
59 Correct 63 ms 32504 KB Ok
60 Correct 43 ms 32136 KB Ok
61 Correct 42 ms 32476 KB Ok
62 Correct 69 ms 33168 KB Ok
63 Correct 46 ms 32212 KB Ok
64 Correct 54 ms 32976 KB Ok
65 Correct 59 ms 32880 KB Ok
66 Correct 46 ms 32432 KB Ok
67 Correct 43 ms 32208 KB Ok
68 Correct 60 ms 32720 KB Ok
69 Correct 104 ms 40132 KB Ok
70 Correct 102 ms 39900 KB Ok
71 Correct 91 ms 38340 KB Ok
72 Correct 105 ms 40016 KB Ok
73 Correct 98 ms 38816 KB Ok
74 Correct 95 ms 39116 KB Ok
75 Correct 98 ms 39440 KB Ok
76 Correct 104 ms 39884 KB Ok
77 Correct 100 ms 38856 KB Ok
78 Correct 109 ms 39624 KB Ok
79 Correct 105 ms 39444 KB Ok
80 Correct 94 ms 38604 KB Ok
81 Correct 111 ms 39840 KB Ok
82 Correct 97 ms 39296 KB Ok
83 Correct 96 ms 39864 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27228 KB Ok
2 Correct 6 ms 27228 KB Ok
3 Correct 6 ms 27228 KB Ok
4 Correct 7 ms 27480 KB Ok
5 Correct 5 ms 27224 KB Ok
6 Correct 6 ms 27228 KB Ok
7 Correct 6 ms 27228 KB Ok
8 Correct 6 ms 27228 KB Ok
9 Correct 6 ms 27228 KB Ok
10 Correct 5 ms 27228 KB Ok
11 Correct 5 ms 27228 KB Ok
12 Correct 6 ms 27228 KB Ok
13 Correct 6 ms 27228 KB Ok
14 Correct 6 ms 27228 KB Ok
15 Correct 6 ms 27228 KB Ok
16 Correct 8 ms 27228 KB Ok
17 Correct 6 ms 27228 KB Ok
18 Correct 9 ms 27720 KB Ok
19 Correct 13 ms 27992 KB Ok
20 Correct 9 ms 27480 KB Ok
21 Correct 13 ms 28252 KB Ok
22 Correct 9 ms 27740 KB Ok
23 Correct 7 ms 27228 KB Ok
24 Correct 6 ms 27228 KB Ok
25 Correct 6 ms 27224 KB Ok
26 Correct 6 ms 27232 KB Ok
27 Correct 5 ms 27224 KB Ok
28 Correct 6 ms 27228 KB Ok
29 Correct 6 ms 27228 KB Ok
30 Correct 5 ms 27228 KB Ok
31 Correct 6 ms 27228 KB Ok
32 Correct 5 ms 27308 KB Ok
33 Correct 6 ms 27316 KB Ok
34 Correct 6 ms 27228 KB Ok
35 Correct 6 ms 27228 KB Ok
36 Correct 6 ms 27224 KB Ok
37 Correct 6 ms 27228 KB Ok
38 Correct 6 ms 27228 KB Ok
39 Correct 77 ms 41160 KB Ok
40 Correct 57 ms 40648 KB Ok
41 Correct 100 ms 43720 KB Ok
42 Correct 79 ms 41416 KB Ok
43 Correct 52 ms 36764 KB Ok
44 Correct 85 ms 44900 KB Ok
45 Correct 7 ms 27224 KB Ok
46 Correct 7 ms 27484 KB Ok
47 Correct 7 ms 27228 KB Ok
48 Correct 6 ms 27484 KB Ok
49 Correct 7 ms 27448 KB Ok
50 Correct 7 ms 27224 KB Ok
51 Correct 7 ms 27228 KB Ok
52 Correct 7 ms 27256 KB Ok
53 Correct 7 ms 27228 KB Ok
54 Correct 7 ms 27464 KB Ok
55 Correct 9 ms 27484 KB Ok
56 Correct 8 ms 27564 KB Ok
57 Correct 9 ms 27508 KB Ok
58 Correct 8 ms 27484 KB Ok
59 Correct 8 ms 27484 KB Ok
60 Correct 8 ms 27484 KB Ok
61 Correct 8 ms 27484 KB Ok
62 Correct 8 ms 27484 KB Ok
63 Correct 8 ms 27484 KB Ok
64 Correct 8 ms 27484 KB Ok
65 Correct 49 ms 32684 KB Ok
66 Correct 62 ms 33032 KB Ok
67 Correct 53 ms 32980 KB Ok
68 Correct 44 ms 31956 KB Ok
69 Correct 51 ms 32904 KB Ok
70 Correct 63 ms 32504 KB Ok
71 Correct 43 ms 32136 KB Ok
72 Correct 42 ms 32476 KB Ok
73 Correct 69 ms 33168 KB Ok
74 Correct 46 ms 32212 KB Ok
75 Correct 54 ms 32976 KB Ok
76 Correct 59 ms 32880 KB Ok
77 Correct 46 ms 32432 KB Ok
78 Correct 43 ms 32208 KB Ok
79 Correct 60 ms 32720 KB Ok
80 Correct 104 ms 40132 KB Ok
81 Correct 102 ms 39900 KB Ok
82 Correct 91 ms 38340 KB Ok
83 Correct 105 ms 40016 KB Ok
84 Correct 98 ms 38816 KB Ok
85 Correct 95 ms 39116 KB Ok
86 Correct 98 ms 39440 KB Ok
87 Correct 104 ms 39884 KB Ok
88 Correct 100 ms 38856 KB Ok
89 Correct 109 ms 39624 KB Ok
90 Correct 105 ms 39444 KB Ok
91 Correct 94 ms 38604 KB Ok
92 Correct 111 ms 39840 KB Ok
93 Correct 97 ms 39296 KB Ok
94 Correct 96 ms 39864 KB Ok
95 Correct 135 ms 41208 KB Ok
96 Correct 190 ms 48456 KB Ok
97 Correct 168 ms 44812 KB Ok
98 Correct 150 ms 44072 KB Ok
99 Correct 140 ms 43968 KB Ok
100 Correct 148 ms 44364 KB Ok
101 Correct 152 ms 46020 KB Ok
102 Correct 155 ms 44740 KB Ok
103 Correct 148 ms 45804 KB Ok
104 Correct 173 ms 47296 KB Ok
105 Correct 166 ms 47868 KB Ok
106 Correct 140 ms 46784 KB Ok
107 Correct 187 ms 46796 KB Ok
108 Correct 177 ms 48064 KB Ok
109 Correct 159 ms 48348 KB Ok
110 Correct 747 ms 81344 KB Ok
111 Correct 881 ms 82528 KB Ok
112 Correct 1020 ms 78524 KB Ok
113 Correct 814 ms 81428 KB Ok
114 Correct 914 ms 77848 KB Ok
115 Correct 1046 ms 82580 KB Ok
116 Correct 1036 ms 82128 KB Ok
117 Correct 752 ms 82260 KB Ok
118 Correct 746 ms 76992 KB Ok
119 Correct 879 ms 81400 KB Ok
120 Correct 901 ms 82320 KB Ok
121 Correct 678 ms 79948 KB Ok
122 Correct 860 ms 82048 KB Ok
123 Correct 764 ms 80292 KB Ok
124 Correct 846 ms 78132 KB Ok
125 Correct 274 ms 65476 KB Ok