oj.uz

Submission #343745

# Submission time Handle Problem Language Result Execution time Memory
343745 2021-01-04T12:54:36 Z Rakhmand Nice sequence (IZhO18_sequence) C++14
76 / 100
 1840 ms 31360 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 = 2e5 + 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;
    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 4 ms 4972 KB Ok
2 Correct 4 ms 4972 KB Ok
3 Correct 4 ms 4972 KB Ok
4 Correct 4 ms 4972 KB Ok
5 Correct 4 ms 4972 KB Ok
6 Correct 4 ms 4992 KB Ok
7 Correct 4 ms 4972 KB Ok
8 Correct 4 ms 4992 KB Ok
9 Correct 4 ms 4972 KB Ok
10 Correct 4 ms 5080 KB Ok
11 Correct 4 ms 4972 KB Ok
12 Correct 4 ms 4972 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 14828 KB Ok
2 Correct 57 ms 14828 KB Ok
3 Correct 50 ms 14828 KB Ok
4 Correct 54 ms 14828 KB Ok
5 Correct 52 ms 14828 KB Ok
6 Correct 51 ms 14828 KB Ok
7 Correct 65 ms 15084 KB Ok
8 Correct 57 ms 15084 KB Ok
9 Correct 70 ms 15468 KB Ok
10 Correct 59 ms 15084 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 14828 KB Ok
2 Correct 4 ms 4972 KB Ok
3 Correct 42 ms 14828 KB Ok
4 Correct 57 ms 14828 KB Ok
5 Correct 52 ms 14848 KB Ok
6 Correct 62 ms 14828 KB Ok
7 Correct 47 ms 14828 KB Ok
8 Correct 70 ms 14956 KB Ok
9 Correct 54 ms 14828 KB Ok
10 Correct 62 ms 14828 KB Ok
11 Correct 55 ms 14828 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 14828 KB Ok
2 Correct 80 ms 14848 KB Ok
3 Correct 85 ms 14828 KB Ok
4 Correct 92 ms 14828 KB Ok
5 Correct 92 ms 14828 KB Ok
6 Correct 494 ms 26212 KB Ok
7 Correct 475 ms 28896 KB Ok
8 Correct 868 ms 31360 KB Ok
9 Correct 609 ms 28384 KB Ok
10 Correct 328 ms 19556 KB Ok
11 Correct 486 ms 30308 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Ok
2 Correct 4 ms 4972 KB Ok
3 Correct 4 ms 4972 KB Ok
4 Correct 4 ms 4972 KB Ok
5 Correct 4 ms 4972 KB Ok
6 Correct 4 ms 4992 KB Ok
7 Correct 4 ms 4972 KB Ok
8 Correct 4 ms 4992 KB Ok
9 Correct 4 ms 4972 KB Ok
10 Correct 4 ms 5080 KB Ok
11 Correct 4 ms 4972 KB Ok
12 Correct 4 ms 4972 KB Ok
13 Correct 25 ms 14828 KB Ok
14 Correct 4 ms 4972 KB Ok
15 Correct 42 ms 14828 KB Ok
16 Correct 57 ms 14828 KB Ok
17 Correct 52 ms 14848 KB Ok
18 Correct 62 ms 14828 KB Ok
19 Correct 47 ms 14828 KB Ok
20 Correct 70 ms 14956 KB Ok
21 Correct 54 ms 14828 KB Ok
22 Correct 62 ms 14828 KB Ok
23 Correct 55 ms 14828 KB Ok
24 Correct 23 ms 8684 KB Ok
25 Correct 27 ms 8812 KB Ok
26 Correct 28 ms 9068 KB Ok
27 Correct 32 ms 9068 KB Ok
28 Correct 26 ms 8684 KB Ok
29 Correct 27 ms 10732 KB Ok
30 Correct 28 ms 8684 KB Ok
31 Correct 33 ms 8812 KB Ok
32 Correct 34 ms 8684 KB Ok
33 Correct 30 ms 8940 KB Ok
34 Correct 112 ms 14956 KB Ok
35 Correct 154 ms 14956 KB Ok
36 Correct 120 ms 15084 KB Ok
37 Correct 151 ms 15084 KB Ok
38 Correct 128 ms 14956 KB Ok
39 Correct 113 ms 14956 KB Ok
40 Correct 159 ms 15212 KB Ok
41 Correct 155 ms 14956 KB Ok
42 Correct 122 ms 14956 KB Ok
43 Correct 149 ms 15004 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Ok
2 Correct 4 ms 4972 KB Ok
3 Correct 4 ms 4972 KB Ok
4 Correct 4 ms 4972 KB Ok
5 Correct 4 ms 4972 KB Ok
6 Correct 4 ms 4992 KB Ok
7 Correct 4 ms 4972 KB Ok
8 Correct 4 ms 4992 KB Ok
9 Correct 4 ms 4972 KB Ok
10 Correct 4 ms 5080 KB Ok
11 Correct 4 ms 4972 KB Ok
12 Correct 4 ms 4972 KB Ok
13 Correct 50 ms 14828 KB Ok
14 Correct 57 ms 14828 KB Ok
15 Correct 50 ms 14828 KB Ok
16 Correct 54 ms 14828 KB Ok
17 Correct 52 ms 14828 KB Ok
18 Correct 51 ms 14828 KB Ok
19 Correct 65 ms 15084 KB Ok
20 Correct 57 ms 15084 KB Ok
21 Correct 70 ms 15468 KB Ok
22 Correct 59 ms 15084 KB Ok
23 Correct 25 ms 14828 KB Ok
24 Correct 4 ms 4972 KB Ok
25 Correct 42 ms 14828 KB Ok
26 Correct 57 ms 14828 KB Ok
27 Correct 52 ms 14848 KB Ok
28 Correct 62 ms 14828 KB Ok
29 Correct 47 ms 14828 KB Ok
30 Correct 70 ms 14956 KB Ok
31 Correct 54 ms 14828 KB Ok
32 Correct 62 ms 14828 KB Ok
33 Correct 55 ms 14828 KB Ok
34 Correct 23 ms 8684 KB Ok
35 Correct 27 ms 8812 KB Ok
36 Correct 28 ms 9068 KB Ok
37 Correct 32 ms 9068 KB Ok
38 Correct 26 ms 8684 KB Ok
39 Correct 27 ms 10732 KB Ok
40 Correct 28 ms 8684 KB Ok
41 Correct 33 ms 8812 KB Ok
42 Correct 34 ms 8684 KB Ok
43 Correct 30 ms 8940 KB Ok
44 Correct 112 ms 14956 KB Ok
45 Correct 154 ms 14956 KB Ok
46 Correct 120 ms 15084 KB Ok
47 Correct 151 ms 15084 KB Ok
48 Correct 128 ms 14956 KB Ok
49 Correct 113 ms 14956 KB Ok
50 Correct 159 ms 15212 KB Ok
51 Correct 155 ms 14956 KB Ok
52 Correct 122 ms 14956 KB Ok
53 Correct 149 ms 15004 KB Ok
54 Correct 175 ms 11472 KB Ok
55 Correct 218 ms 11748 KB Ok
56 Correct 208 ms 11752 KB Ok
57 Correct 140 ms 11036 KB Ok
58 Correct 183 ms 11236 KB Ok
59 Correct 159 ms 11108 KB Ok
60 Correct 137 ms 10852 KB Ok
61 Correct 157 ms 11108 KB Ok
62 Correct 215 ms 11492 KB Ok
63 Correct 155 ms 11108 KB Ok
64 Correct 217 ms 11748 KB Ok
65 Correct 188 ms 11356 KB Ok
66 Correct 165 ms 11236 KB Ok
67 Correct 139 ms 11172 KB Ok
68 Correct 171 ms 11364 KB Ok
69 Correct 1105 ms 22080 KB Ok
70 Correct 1840 ms 22628 KB Ok
71 Correct 923 ms 22244 KB Ok
72 Correct 1081 ms 22152 KB Ok
73 Correct 1223 ms 22300 KB Ok
74 Correct 816 ms 22096 KB Ok
75 Correct 769 ms 21648 KB Ok
76 Correct 1653 ms 22532 KB Ok
77 Correct 687 ms 21788 KB Ok
78 Correct 1667 ms 22628 KB Ok
79 Correct 1543 ms 22372 KB Ok
80 Correct 916 ms 22500 KB Ok
81 Correct 1122 ms 22372 KB Ok
82 Correct 1033 ms 22268 KB Ok
83 Correct 782 ms 21732 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Ok
2 Correct 4 ms 4972 KB Ok
3 Correct 4 ms 4972 KB Ok
4 Correct 4 ms 4972 KB Ok
5 Correct 4 ms 4972 KB Ok
6 Correct 4 ms 4992 KB Ok
7 Correct 4 ms 4972 KB Ok
8 Correct 4 ms 4992 KB Ok
9 Correct 4 ms 4972 KB Ok
10 Correct 4 ms 5080 KB Ok
11 Correct 4 ms 4972 KB Ok
12 Correct 4 ms 4972 KB Ok
13 Correct 50 ms 14828 KB Ok
14 Correct 57 ms 14828 KB Ok
15 Correct 50 ms 14828 KB Ok
16 Correct 54 ms 14828 KB Ok
17 Correct 52 ms 14828 KB Ok
18 Correct 51 ms 14828 KB Ok
19 Correct 65 ms 15084 KB Ok
20 Correct 57 ms 15084 KB Ok
21 Correct 70 ms 15468 KB Ok
22 Correct 59 ms 15084 KB Ok
23 Correct 25 ms 14828 KB Ok
24 Correct 4 ms 4972 KB Ok
25 Correct 42 ms 14828 KB Ok
26 Correct 57 ms 14828 KB Ok
27 Correct 52 ms 14848 KB Ok
28 Correct 62 ms 14828 KB Ok
29 Correct 47 ms 14828 KB Ok
30 Correct 70 ms 14956 KB Ok
31 Correct 54 ms 14828 KB Ok
32 Correct 62 ms 14828 KB Ok
33 Correct 55 ms 14828 KB Ok
34 Correct 71 ms 14828 KB Ok
35 Correct 80 ms 14848 KB Ok
36 Correct 85 ms 14828 KB Ok
37 Correct 92 ms 14828 KB Ok
38 Correct 92 ms 14828 KB Ok
39 Correct 494 ms 26212 KB Ok
40 Correct 475 ms 28896 KB Ok
41 Correct 868 ms 31360 KB Ok
42 Correct 609 ms 28384 KB Ok
43 Correct 328 ms 19556 KB Ok
44 Correct 486 ms 30308 KB Ok
45 Correct 23 ms 8684 KB Ok
46 Correct 27 ms 8812 KB Ok
47 Correct 28 ms 9068 KB Ok
48 Correct 32 ms 9068 KB Ok
49 Correct 26 ms 8684 KB Ok
50 Correct 27 ms 10732 KB Ok
51 Correct 28 ms 8684 KB Ok
52 Correct 33 ms 8812 KB Ok
53 Correct 34 ms 8684 KB Ok
54 Correct 30 ms 8940 KB Ok
55 Correct 112 ms 14956 KB Ok
56 Correct 154 ms 14956 KB Ok
57 Correct 120 ms 15084 KB Ok
58 Correct 151 ms 15084 KB Ok
59 Correct 128 ms 14956 KB Ok
60 Correct 113 ms 14956 KB Ok
61 Correct 159 ms 15212 KB Ok
62 Correct 155 ms 14956 KB Ok
63 Correct 122 ms 14956 KB Ok
64 Correct 149 ms 15004 KB Ok
65 Correct 175 ms 11472 KB Ok
66 Correct 218 ms 11748 KB Ok
67 Correct 208 ms 11752 KB Ok
68 Correct 140 ms 11036 KB Ok
69 Correct 183 ms 11236 KB Ok
70 Correct 159 ms 11108 KB Ok
71 Correct 137 ms 10852 KB Ok
72 Correct 157 ms 11108 KB Ok
73 Correct 215 ms 11492 KB Ok
74 Correct 155 ms 11108 KB Ok
75 Correct 217 ms 11748 KB Ok
76 Correct 188 ms 11356 KB Ok
77 Correct 165 ms 11236 KB Ok
78 Correct 139 ms 11172 KB Ok
79 Correct 171 ms 11364 KB Ok
80 Correct 1105 ms 22080 KB Ok
81 Correct 1840 ms 22628 KB Ok
82 Correct 923 ms 22244 KB Ok
83 Correct 1081 ms 22152 KB Ok
84 Correct 1223 ms 22300 KB Ok
85 Correct 816 ms 22096 KB Ok
86 Correct 769 ms 21648 KB Ok
87 Correct 1653 ms 22532 KB Ok
88 Correct 687 ms 21788 KB Ok
89 Correct 1667 ms 22628 KB Ok
90 Correct 1543 ms 22372 KB Ok
91 Correct 916 ms 22500 KB Ok
92 Correct 1122 ms 22372 KB Ok
93 Correct 1033 ms 22268 KB Ok
94 Correct 782 ms 21732 KB Ok
95 Incorrect 310 ms 18020 KB Jury has the better answer : jans = 239234, pans = 200109
96 Halted 0 ms 0 KB -