oj.uz

Submission #343752

# Submission time Handle Problem Language Result Execution time Memory
343752 2021-01-04T12:56:21 Z Rakhmand Nice sequence (IZhO18_sequence) C++14
58 / 100
 2000 ms 80780 KB 
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>

using namespace std;

#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define no_answer {cout << "NO"; exit(0);}
#define FOR(i, start, finish, k) for(llong i = start; i <= finish; i += k)

const long long mxn = 1e6 + 110;
const long long mnn = 1e3 + 2;
const long long mod = 1e9 + 7;
const long long inf = 1e18;
const long long OO = 1e8;

typedef long long llong;
typedef unsigned long long ullong;

int n, m, pr[mxn], a[mxn];
int used[mxn];
vector<int> g[mxn], top;

bool dfs(int x){
    used[x] = 1;
    bool ok = true;
    for(auto to : g[x]){
        if(used[to] == 0) ok = (ok & dfs(to));
        else if(used[to] == 1){
            ok = false;
        }else{
            continue;
        }
    }
    used[x] = 2;
    return ok;
    
}

bool check(int k){
    for(int i = 1; i <= k; i++){
        used[i] = 0;
        g[i].clear();
    }
    for(int i = 1; i + min(n, m) <= k; i++){
        if(i + n <= k)
            g[i].push_back(i + n);
        if(i + m <= k)
            g[i + m].push_back(i);
    }
    return dfs(1);
}

void dfss(int x){
    used[x] = 1;
    for(auto to : g[x]){
        if(used[to] == 0){
            dfss(to);
        }
    }
    top.push_back(x);
}

void solve(){
    cin >> n >> m;
    if(n == m){
        cout << n - 1 << nl;
        for(int i = 1; i < n; i++){
            cout << 1 << ' ';
        }
        cout << nl;
        return ;
    }
    if(n == 1 || m % n == 0){
        cout << m - 1 << nl;
        for(int i = 1; i <= m - 1; i++) cout << -1 << ' ';
        cout << nl;
        return ;
    }
    if(m == 1 || n % m == 0){
        cout << n - 1 << nl;
        for(int i = 1; i <= n - 1; i++) cout << 1 << ' ';
        cout << nl;
        return ;
    }
    int l = 0, r = mxn - 1;
    while(r - l > 1){
        int m = (l + r) / 2;
        if(check(m)){
            l = m;
        }else{
            r = m;
        }
    }
    int ans = -1;
    if(check(r)) ans = r;
    else ans = l;
    for(int i = 1; i <= ans; i++){
        used[i] = 0;
    }
    top.clear();
    cout << ans - 1 << nl;
    for(int i = 1; i <= ans; i++){
        if(used[i] == 0){
            dfss(i);
        }
    }
    reverse(top.begin(), top.end());
    for(int i = 0; i < top.size(); i++){
        pr[top[i]] = OO - i;
    }
    for(int i = 2; i <= ans; i++){
        pr[i] -= pr[1];
    }
    pr[1] = 0;
    for(int i = 2; i <= ans; i++){
        a[i] = pr[i] - pr[i - 1];
    }
    for(int i = 2; i <= ans; i++){
        cout << a[i] << ' ';
    }
    cout << nl;
}

int main() {
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

/*
 5 4 4
 1 2
 3 1
 4 3
 5 3
 4 5 2 3
 2 1 3 1
 1 3 5
 2 3 4 5
 2 1 3 1
 
 6 1
 1 1 2
 3 2 4 2
 1 3 5
 3 2 3 1
 2 1
 3 0 3 1
 
 6 0
 1 3 10
 1 3 5
 3 6 10 6
 2 1
 1 3 10
 3 6 4 2
 */

Compilation message

sequence.cpp: In function 'void solve()':
sequence.cpp:135:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for(int i = 0; i < top.size(); i++){
      |                    ~~^~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Ok
2 Correct 17 ms 23788 KB Ok
3 Correct 16 ms 23788 KB Ok
4 Correct 18 ms 23788 KB Ok
5 Correct 17 ms 23788 KB Ok
6 Correct 17 ms 23788 KB Ok
7 Correct 18 ms 23788 KB Ok
8 Correct 17 ms 23788 KB Ok
9 Correct 17 ms 23788 KB Ok
10 Correct 17 ms 23788 KB Ok
11 Correct 17 ms 23788 KB Ok
12 Correct 20 ms 23788 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 72684 KB Ok
2 Correct 320 ms 72684 KB Ok
3 Correct 312 ms 72872 KB Ok
4 Correct 320 ms 72684 KB Ok
5 Correct 302 ms 72812 KB Ok
6 Correct 304 ms 72812 KB Ok
7 Correct 297 ms 73200 KB Ok
8 Correct 293 ms 72948 KB Ok
9 Correct 318 ms 73336 KB Ok
10 Correct 299 ms 72940 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 72684 KB Ok
2 Correct 18 ms 23788 KB Ok
3 Correct 236 ms 72812 KB Ok
4 Correct 326 ms 72684 KB Ok
5 Correct 312 ms 72812 KB Ok
6 Correct 379 ms 72684 KB Ok
7 Correct 287 ms 72684 KB Ok
8 Correct 445 ms 72684 KB Ok
9 Correct 339 ms 72812 KB Ok
10 Correct 384 ms 72684 KB Ok
11 Correct 313 ms 72684 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 72684 KB Ok
2 Correct 545 ms 72684 KB Ok
3 Correct 511 ms 72684 KB Ok
4 Correct 583 ms 72684 KB Ok
5 Correct 539 ms 72684 KB Ok
6 Correct 864 ms 78320 KB Ok
7 Correct 842 ms 77280 KB Ok
8 Correct 1256 ms 80780 KB Ok
9 Correct 993 ms 79348 KB Ok
10 Correct 642 ms 75364 KB Ok
11 Correct 879 ms 78688 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Ok
2 Correct 17 ms 23788 KB Ok
3 Correct 16 ms 23788 KB Ok
4 Correct 18 ms 23788 KB Ok
5 Correct 17 ms 23788 KB Ok
6 Correct 17 ms 23788 KB Ok
7 Correct 18 ms 23788 KB Ok
8 Correct 17 ms 23788 KB Ok
9 Correct 17 ms 23788 KB Ok
10 Correct 17 ms 23788 KB Ok
11 Correct 17 ms 23788 KB Ok
12 Correct 20 ms 23788 KB Ok
13 Correct 119 ms 72684 KB Ok
14 Correct 18 ms 23788 KB Ok
15 Correct 236 ms 72812 KB Ok
16 Correct 326 ms 72684 KB Ok
17 Correct 312 ms 72812 KB Ok
18 Correct 379 ms 72684 KB Ok
19 Correct 287 ms 72684 KB Ok
20 Correct 445 ms 72684 KB Ok
21 Correct 339 ms 72812 KB Ok
22 Correct 384 ms 72684 KB Ok
23 Correct 313 ms 72684 KB Ok
24 Correct 108 ms 41580 KB Ok
25 Correct 128 ms 42092 KB Ok
26 Correct 135 ms 43628 KB Ok
27 Correct 159 ms 43884 KB Ok
28 Correct 133 ms 42092 KB Ok
29 Correct 155 ms 51948 KB Ok
30 Correct 126 ms 42220 KB Ok
31 Correct 161 ms 42092 KB Ok
32 Correct 157 ms 41984 KB Ok
33 Correct 154 ms 43196 KB Ok
34 Correct 636 ms 73068 KB Ok
35 Correct 914 ms 73068 KB Ok
36 Correct 715 ms 72940 KB Ok
37 Correct 877 ms 73012 KB Ok
38 Correct 791 ms 72940 KB Ok
39 Correct 637 ms 72932 KB Ok
40 Correct 915 ms 72940 KB Ok
41 Correct 870 ms 72940 KB Ok
42 Correct 707 ms 72812 KB Ok
43 Correct 869 ms 73068 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Ok
2 Correct 17 ms 23788 KB Ok
3 Correct 16 ms 23788 KB Ok
4 Correct 18 ms 23788 KB Ok
5 Correct 17 ms 23788 KB Ok
6 Correct 17 ms 23788 KB Ok
7 Correct 18 ms 23788 KB Ok
8 Correct 17 ms 23788 KB Ok
9 Correct 17 ms 23788 KB Ok
10 Correct 17 ms 23788 KB Ok
11 Correct 17 ms 23788 KB Ok
12 Correct 20 ms 23788 KB Ok
13 Correct 286 ms 72684 KB Ok
14 Correct 320 ms 72684 KB Ok
15 Correct 312 ms 72872 KB Ok
16 Correct 320 ms 72684 KB Ok
17 Correct 302 ms 72812 KB Ok
18 Correct 304 ms 72812 KB Ok
19 Correct 297 ms 73200 KB Ok
20 Correct 293 ms 72948 KB Ok
21 Correct 318 ms 73336 KB Ok
22 Correct 299 ms 72940 KB Ok
23 Correct 119 ms 72684 KB Ok
24 Correct 18 ms 23788 KB Ok
25 Correct 236 ms 72812 KB Ok
26 Correct 326 ms 72684 KB Ok
27 Correct 312 ms 72812 KB Ok
28 Correct 379 ms 72684 KB Ok
29 Correct 287 ms 72684 KB Ok
30 Correct 445 ms 72684 KB Ok
31 Correct 339 ms 72812 KB Ok
32 Correct 384 ms 72684 KB Ok
33 Correct 313 ms 72684 KB Ok
34 Correct 108 ms 41580 KB Ok
35 Correct 128 ms 42092 KB Ok
36 Correct 135 ms 43628 KB Ok
37 Correct 159 ms 43884 KB Ok
38 Correct 133 ms 42092 KB Ok
39 Correct 155 ms 51948 KB Ok
40 Correct 126 ms 42220 KB Ok
41 Correct 161 ms 42092 KB Ok
42 Correct 157 ms 41984 KB Ok
43 Correct 154 ms 43196 KB Ok
44 Correct 636 ms 73068 KB Ok
45 Correct 914 ms 73068 KB Ok
46 Correct 715 ms 72940 KB Ok
47 Correct 877 ms 73012 KB Ok
48 Correct 791 ms 72940 KB Ok
49 Correct 637 ms 72932 KB Ok
50 Correct 915 ms 72940 KB Ok
51 Correct 870 ms 72940 KB Ok
52 Correct 707 ms 72812 KB Ok
53 Correct 869 ms 73068 KB Ok
54 Correct 311 ms 44388 KB Ok
55 Correct 391 ms 44644 KB Ok
56 Correct 350 ms 44796 KB Ok
57 Correct 258 ms 43876 KB Ok
58 Correct 322 ms 44148 KB Ok
59 Correct 284 ms 44004 KB Ok
60 Correct 259 ms 43896 KB Ok
61 Correct 287 ms 44004 KB Ok
62 Correct 386 ms 44516 KB Ok
63 Correct 275 ms 44004 KB Ok
64 Correct 378 ms 44772 KB Ok
65 Correct 343 ms 44300 KB Ok
66 Correct 303 ms 44132 KB Ok
67 Correct 251 ms 44260 KB Ok
68 Correct 313 ms 44260 KB Ok
69 Execution timed out 2087 ms 78320 KB Time limit exceeded
70 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Ok
2 Correct 17 ms 23788 KB Ok
3 Correct 16 ms 23788 KB Ok
4 Correct 18 ms 23788 KB Ok
5 Correct 17 ms 23788 KB Ok
6 Correct 17 ms 23788 KB Ok
7 Correct 18 ms 23788 KB Ok
8 Correct 17 ms 23788 KB Ok
9 Correct 17 ms 23788 KB Ok
10 Correct 17 ms 23788 KB Ok
11 Correct 17 ms 23788 KB Ok
12 Correct 20 ms 23788 KB Ok
13 Correct 286 ms 72684 KB Ok
14 Correct 320 ms 72684 KB Ok
15 Correct 312 ms 72872 KB Ok
16 Correct 320 ms 72684 KB Ok
17 Correct 302 ms 72812 KB Ok
18 Correct 304 ms 72812 KB Ok
19 Correct 297 ms 73200 KB Ok
20 Correct 293 ms 72948 KB Ok
21 Correct 318 ms 73336 KB Ok
22 Correct 299 ms 72940 KB Ok
23 Correct 119 ms 72684 KB Ok
24 Correct 18 ms 23788 KB Ok
25 Correct 236 ms 72812 KB Ok
26 Correct 326 ms 72684 KB Ok
27 Correct 312 ms 72812 KB Ok
28 Correct 379 ms 72684 KB Ok
29 Correct 287 ms 72684 KB Ok
30 Correct 445 ms 72684 KB Ok
31 Correct 339 ms 72812 KB Ok
32 Correct 384 ms 72684 KB Ok
33 Correct 313 ms 72684 KB Ok
34 Correct 416 ms 72684 KB Ok
35 Correct 545 ms 72684 KB Ok
36 Correct 511 ms 72684 KB Ok
37 Correct 583 ms 72684 KB Ok
38 Correct 539 ms 72684 KB Ok
39 Correct 864 ms 78320 KB Ok
40 Correct 842 ms 77280 KB Ok
41 Correct 1256 ms 80780 KB Ok
42 Correct 993 ms 79348 KB Ok
43 Correct 642 ms 75364 KB Ok
44 Correct 879 ms 78688 KB Ok
45 Correct 108 ms 41580 KB Ok
46 Correct 128 ms 42092 KB Ok
47 Correct 135 ms 43628 KB Ok
48 Correct 159 ms 43884 KB Ok
49 Correct 133 ms 42092 KB Ok
50 Correct 155 ms 51948 KB Ok
51 Correct 126 ms 42220 KB Ok
52 Correct 161 ms 42092 KB Ok
53 Correct 157 ms 41984 KB Ok
54 Correct 154 ms 43196 KB Ok
55 Correct 636 ms 73068 KB Ok
56 Correct 914 ms 73068 KB Ok
57 Correct 715 ms 72940 KB Ok
58 Correct 877 ms 73012 KB Ok
59 Correct 791 ms 72940 KB Ok
60 Correct 637 ms 72932 KB Ok
61 Correct 915 ms 72940 KB Ok
62 Correct 870 ms 72940 KB Ok
63 Correct 707 ms 72812 KB Ok
64 Correct 869 ms 73068 KB Ok
65 Correct 311 ms 44388 KB Ok
66 Correct 391 ms 44644 KB Ok
67 Correct 350 ms 44796 KB Ok
68 Correct 258 ms 43876 KB Ok
69 Correct 322 ms 44148 KB Ok
70 Correct 284 ms 44004 KB Ok
71 Correct 259 ms 43896 KB Ok
72 Correct 287 ms 44004 KB Ok
73 Correct 386 ms 44516 KB Ok
74 Correct 275 ms 44004 KB Ok
75 Correct 378 ms 44772 KB Ok
76 Correct 343 ms 44300 KB Ok
77 Correct 303 ms 44132 KB Ok
78 Correct 251 ms 44260 KB Ok
79 Correct 313 ms 44260 KB Ok
80 Execution timed out 2087 ms 78320 KB Time limit exceeded
81 Halted 0 ms 0 KB -