oj.uz

Submission #496342

# Submission time Handle Problem Language Result Execution time Memory
496342 2021-12-21T06:07:31 Z armashka Nice sequence (IZhO18_sequence) C++17
34 / 100
 990 ms 262148 KB 
#include <bits/stdc++.h>
 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#define fast ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define all(v) v.begin(),v.end()
#define pb push_back
#define sz size()
#define ft first
#define sd second
 
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef unsigned long long ull;
 
const int N = 5e5 + 5;
const ll M = 1e8;
const ll inf = 1e9;
const ll mod = 1e9;
const double Pi = acos(-1); 
 
ll binpow(ll x, ll ti) { ll res = 1;while (ti){if(ti & 1)res *= x;x *= x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll binmul(ll x, ll ti) { ll res = 0;while (ti){if(ti & 1)res += x;x += x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll nok(ll a, ll b) { return (a*b)/__gcd(abs(a),abs(b)) * (a*b > 0 ? 1 : -1); }
bool odd(ll n) { return (n % 2 == 1); }
bool even(ll n) { return (n % 2 == 0); }            
 
int n, m, used[N], pr[N], len;
vector <int> g[N], order;
bool ok;
 
void qfs(int v, int mx) {
    used[v] = 1;
    for (auto to : g[v]) { 
        if (to > mx) continue;
        qfs(to, mx);
    }
    order.pb(v);
}
 
const void solve(/*Armashka*/) {
    cin >> n >> m;
    ll len = n + m - 1 - __gcd(n, m);
	for (int i = 0; i <= len; ++ i) used[i] = 0;
	for (int i = 0; i <= len; ++ i) {
        if (i >= n) g[i - n].pb(i);
        if (i >= m) g[i].pb(i - m);
    }
    for (int i = 0; i <= len; ++ i) {
       if (!used[i]) qfs(i, len);
    }
    reverse(all(order));
    for (int i = 0; i <= len; ++ i) {
        pr[order[i]] = i;
    } 
    cout << len << "\n";
    for (int i = 1; i <= len; ++ i) {
        cout << -(pr[i] - pr[i - 1]) << " ";
    }
    cout << "\n";
    for (int i = 0; i <= 4e5; ++ i) pr[i] = 0, g[i].clear();
    order.clear();
}
 
signed main() {
    fast;
    //freopen("divide.in", "r", stdin);
    //freopen("divide.out", "w", stdout);
    int tt = 1;
    cin >> tt;
    while (tt --) {
        solve();
    }
}
 
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 13632 KB Ok
2 Correct 19 ms 13564 KB Ok
3 Correct 17 ms 13636 KB Ok
4 Correct 17 ms 13516 KB Ok
5 Correct 16 ms 13516 KB Ok
6 Correct 15 ms 13636 KB Ok
7 Correct 16 ms 13516 KB Ok
8 Correct 15 ms 13636 KB Ok
9 Correct 15 ms 13632 KB Ok
10 Correct 15 ms 13632 KB Ok
11 Correct 15 ms 13632 KB Ok
12 Correct 16 ms 13632 KB Ok

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 13516 KB Ok
2 Correct 15 ms 13628 KB Ok
3 Correct 15 ms 13640 KB Ok
4 Correct 15 ms 13516 KB Ok
5 Correct 15 ms 13632 KB Ok
6 Correct 60 ms 22060 KB Ok
7 Correct 990 ms 146016 KB Ok
8 Correct 166 ms 46948 KB Ok
9 Runtime error 467 ms 262148 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 13516 KB Ok
2 Correct 15 ms 13516 KB Ok
3 Correct 15 ms 13616 KB Ok
4 Correct 15 ms 13632 KB Ok
5 Correct 15 ms 13632 KB Ok
6 Correct 15 ms 13560 KB Ok
7 Correct 15 ms 13516 KB Ok
8 Correct 15 ms 13516 KB Ok
9 Correct 18 ms 13636 KB Ok
10 Correct 18 ms 13516 KB Ok
11 Correct 15 ms 13628 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 13516 KB Ok
2 Correct 15 ms 13628 KB Ok
3 Correct 16 ms 13516 KB Ok
4 Correct 16 ms 13516 KB Ok
5 Correct 15 ms 13640 KB Ok
6 Runtime error 477 ms 262148 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 13632 KB Ok
2 Correct 19 ms 13564 KB Ok
3 Correct 17 ms 13636 KB Ok
4 Correct 17 ms 13516 KB Ok
5 Correct 16 ms 13516 KB Ok
6 Correct 15 ms 13636 KB Ok
7 Correct 16 ms 13516 KB Ok
8 Correct 15 ms 13636 KB Ok
9 Correct 15 ms 13632 KB Ok
10 Correct 15 ms 13632 KB Ok
11 Correct 15 ms 13632 KB Ok
12 Correct 16 ms 13632 KB Ok
13 Correct 9 ms 13516 KB Ok
14 Correct 15 ms 13516 KB Ok
15 Correct 15 ms 13616 KB Ok
16 Correct 15 ms 13632 KB Ok
17 Correct 15 ms 13632 KB Ok
18 Correct 15 ms 13560 KB Ok
19 Correct 15 ms 13516 KB Ok
20 Correct 15 ms 13516 KB Ok
21 Correct 18 ms 13636 KB Ok
22 Correct 18 ms 13516 KB Ok
23 Correct 15 ms 13628 KB Ok
24 Correct 17 ms 13772 KB Ok
25 Correct 17 ms 13976 KB Ok
26 Correct 17 ms 13940 KB Ok
27 Correct 18 ms 13924 KB Ok
28 Correct 18 ms 13776 KB Ok
29 Correct 20 ms 13756 KB Ok
30 Correct 17 ms 13784 KB Ok
31 Correct 18 ms 13772 KB Ok
32 Correct 17 ms 13888 KB Ok
33 Correct 17 ms 13892 KB Ok
34 Correct 24 ms 14536 KB Ok
35 Correct 30 ms 15088 KB Ok
36 Correct 43 ms 22432 KB Ok
37 Correct 27 ms 14616 KB Ok
38 Correct 28 ms 14592 KB Ok
39 Correct 24 ms 14416 KB Ok
40 Correct 39 ms 15136 KB Ok
41 Correct 34 ms 14952 KB Ok
42 Correct 26 ms 14696 KB Ok
43 Correct 25 ms 15044 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 13632 KB Ok
2 Correct 19 ms 13564 KB Ok
3 Correct 17 ms 13636 KB Ok
4 Correct 17 ms 13516 KB Ok
5 Correct 16 ms 13516 KB Ok
6 Correct 15 ms 13636 KB Ok
7 Correct 16 ms 13516 KB Ok
8 Correct 15 ms 13636 KB Ok
9 Correct 15 ms 13632 KB Ok
10 Correct 15 ms 13632 KB Ok
11 Correct 15 ms 13632 KB Ok
12 Correct 16 ms 13632 KB Ok
13 Correct 15 ms 13516 KB Ok
14 Correct 15 ms 13628 KB Ok
15 Correct 15 ms 13640 KB Ok
16 Correct 15 ms 13516 KB Ok
17 Correct 15 ms 13632 KB Ok
18 Correct 60 ms 22060 KB Ok
19 Correct 990 ms 146016 KB Ok
20 Correct 166 ms 46948 KB Ok
21 Runtime error 467 ms 262148 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 13632 KB Ok
2 Correct 19 ms 13564 KB Ok
3 Correct 17 ms 13636 KB Ok
4 Correct 17 ms 13516 KB Ok
5 Correct 16 ms 13516 KB Ok
6 Correct 15 ms 13636 KB Ok
7 Correct 16 ms 13516 KB Ok
8 Correct 15 ms 13636 KB Ok
9 Correct 15 ms 13632 KB Ok
10 Correct 15 ms 13632 KB Ok
11 Correct 15 ms 13632 KB Ok
12 Correct 16 ms 13632 KB Ok
13 Correct 15 ms 13516 KB Ok
14 Correct 15 ms 13628 KB Ok
15 Correct 15 ms 13640 KB Ok
16 Correct 15 ms 13516 KB Ok
17 Correct 15 ms 13632 KB Ok
18 Correct 60 ms 22060 KB Ok
19 Correct 990 ms 146016 KB Ok
20 Correct 166 ms 46948 KB Ok
21 Runtime error 467 ms 262148 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -