oj.uz

Submission #496020

# Submission time Handle Problem Language Result Execution time Memory
496020 2021-12-20T12:01:33 Z armashka Nice sequence (IZhO18_sequence) C++17
34 / 100
 1016 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 dfs(int v, int mx) {
    used[v] = 1;
    for (auto to : g[v]) {
        if (to > mx) continue;
        if (used[to] == 1) {
            ok = 0;
        }
        if (!used[to]) dfs(to, mx);
    }
    used[v] = 2;                                                        
}
 
bool check(int x) {
    ok = 1;
    for (int i = 0; i <= x; ++ i) used[i] = 0;
    for (int i = 0; i <= x; ++ i) {
        if (used[i] == 0) {
            dfs(i, x);
        }
    }
    return 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;
    if (n == 1 && m == 1) {
        cout << "0\n";
        return;
    }
    for (int i = 0; i <= 4e5; ++ i) {
        if (i >= n) g[i - n].pb(i);
        if (i >= m) g[i].pb(i - m);
    }
    int l = 1, r = n + m;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) l = mid + 1, len = mid;
        else r = mid - 1;       
    }
    for (int i = 0; i <= len; ++ i) used[i] = 0;
    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 90 ms 26248 KB Ok
2 Correct 91 ms 26152 KB Ok
3 Correct 87 ms 26112 KB Ok
4 Correct 88 ms 26088 KB Ok
5 Correct 88 ms 26124 KB Ok
6 Correct 90 ms 26136 KB Ok
7 Correct 92 ms 26136 KB Ok
8 Correct 87 ms 26140 KB Ok
9 Correct 87 ms 26028 KB Ok
10 Correct 98 ms 26016 KB Ok
11 Correct 91 ms 26052 KB Ok
12 Correct 84 ms 26180 KB Ok

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 26048 KB Ok
2 Correct 86 ms 26132 KB Ok
3 Correct 85 ms 26100 KB Ok
4 Correct 87 ms 26136 KB Ok
5 Correct 83 ms 26048 KB Ok
6 Correct 129 ms 34480 KB Ok
7 Correct 1016 ms 158168 KB Ok
8 Correct 243 ms 59448 KB Ok
9 Runtime error 502 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 40 ms 26128 KB Ok
2 Correct 81 ms 26144 KB Ok
3 Correct 90 ms 26096 KB Ok
4 Correct 85 ms 26136 KB Ok
5 Correct 82 ms 26140 KB Ok
6 Correct 89 ms 26136 KB Ok
7 Correct 92 ms 26048 KB Ok
8 Correct 88 ms 26020 KB Ok
9 Correct 97 ms 26144 KB Ok
10 Correct 83 ms 26136 KB Ok
11 Correct 84 ms 26044 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 26136 KB Ok
2 Correct 91 ms 26136 KB Ok
3 Correct 88 ms 26056 KB Ok
4 Correct 86 ms 26020 KB Ok
5 Correct 85 ms 26140 KB Ok
6 Runtime error 518 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 90 ms 26248 KB Ok
2 Correct 91 ms 26152 KB Ok
3 Correct 87 ms 26112 KB Ok
4 Correct 88 ms 26088 KB Ok
5 Correct 88 ms 26124 KB Ok
6 Correct 90 ms 26136 KB Ok
7 Correct 92 ms 26136 KB Ok
8 Correct 87 ms 26140 KB Ok
9 Correct 87 ms 26028 KB Ok
10 Correct 98 ms 26016 KB Ok
11 Correct 91 ms 26052 KB Ok
12 Correct 84 ms 26180 KB Ok
13 Correct 40 ms 26128 KB Ok
14 Correct 81 ms 26144 KB Ok
15 Correct 90 ms 26096 KB Ok
16 Correct 85 ms 26136 KB Ok
17 Correct 82 ms 26140 KB Ok
18 Correct 89 ms 26136 KB Ok
19 Correct 92 ms 26048 KB Ok
20 Correct 88 ms 26020 KB Ok
21 Correct 97 ms 26144 KB Ok
22 Correct 83 ms 26136 KB Ok
23 Correct 84 ms 26044 KB Ok
24 Correct 85 ms 26252 KB Ok
25 Correct 88 ms 26384 KB Ok
26 Correct 90 ms 26376 KB Ok
27 Correct 89 ms 26416 KB Ok
28 Correct 94 ms 26224 KB Ok
29 Correct 99 ms 26308 KB Ok
30 Correct 92 ms 26280 KB Ok
31 Correct 98 ms 26148 KB Ok
32 Correct 90 ms 26196 KB Ok
33 Correct 91 ms 26440 KB Ok
34 Correct 102 ms 26960 KB Ok
35 Correct 97 ms 27464 KB Ok
36 Correct 120 ms 34816 KB Ok
37 Correct 97 ms 27068 KB Ok
38 Correct 101 ms 27120 KB Ok
39 Correct 99 ms 26780 KB Ok
40 Correct 100 ms 27624 KB Ok
41 Correct 101 ms 27600 KB Ok
42 Correct 104 ms 26992 KB Ok
43 Correct 112 ms 27476 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 26248 KB Ok
2 Correct 91 ms 26152 KB Ok
3 Correct 87 ms 26112 KB Ok
4 Correct 88 ms 26088 KB Ok
5 Correct 88 ms 26124 KB Ok
6 Correct 90 ms 26136 KB Ok
7 Correct 92 ms 26136 KB Ok
8 Correct 87 ms 26140 KB Ok
9 Correct 87 ms 26028 KB Ok
10 Correct 98 ms 26016 KB Ok
11 Correct 91 ms 26052 KB Ok
12 Correct 84 ms 26180 KB Ok
13 Correct 82 ms 26048 KB Ok
14 Correct 86 ms 26132 KB Ok
15 Correct 85 ms 26100 KB Ok
16 Correct 87 ms 26136 KB Ok
17 Correct 83 ms 26048 KB Ok
18 Correct 129 ms 34480 KB Ok
19 Correct 1016 ms 158168 KB Ok
20 Correct 243 ms 59448 KB Ok
21 Runtime error 502 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 90 ms 26248 KB Ok
2 Correct 91 ms 26152 KB Ok
3 Correct 87 ms 26112 KB Ok
4 Correct 88 ms 26088 KB Ok
5 Correct 88 ms 26124 KB Ok
6 Correct 90 ms 26136 KB Ok
7 Correct 92 ms 26136 KB Ok
8 Correct 87 ms 26140 KB Ok
9 Correct 87 ms 26028 KB Ok
10 Correct 98 ms 26016 KB Ok
11 Correct 91 ms 26052 KB Ok
12 Correct 84 ms 26180 KB Ok
13 Correct 82 ms 26048 KB Ok
14 Correct 86 ms 26132 KB Ok
15 Correct 85 ms 26100 KB Ok
16 Correct 87 ms 26136 KB Ok
17 Correct 83 ms 26048 KB Ok
18 Correct 129 ms 34480 KB Ok
19 Correct 1016 ms 158168 KB Ok
20 Correct 243 ms 59448 KB Ok
21 Runtime error 502 ms 262148 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -