oj.uz

Submission #343758

# Submission time Handle Problem Language Result Execution time Memory
343758 2021-01-04T13:02:28 Z Rakhmand Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 67780 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 = 4e5 + 110;
const long long mnn = 1e3 + 2;
const long long mod = 1e9 + 7;
const long long inf = 1e18;
const long long OO = 1e9;
 
typedef long long llong;
typedef unsigned long long ullong;
 
int n, m;
llong 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 = n + m + 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() {
    ios;
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

Compilation message

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

Subtask #1
6.0 / 6.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9708 KB Ok
2 Correct 8 ms 9708 KB Ok
3 Correct 9 ms 9708 KB Ok
4 Correct 8 ms 9708 KB Ok
5 Correct 7 ms 9708 KB Ok
6 Correct 12 ms 9964 KB Ok
7 Correct 26 ms 11244 KB Ok
8 Correct 15 ms 10368 KB Ok
9 Correct 28 ms 11364 KB Ok
10 Correct 19 ms 10732 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9836 KB Ok
2 Correct 7 ms 9708 KB Ok
3 Correct 9 ms 9708 KB Ok
4 Correct 8 ms 9836 KB Ok
5 Correct 7 ms 9708 KB Ok
6 Correct 8 ms 9708 KB Ok
7 Correct 8 ms 9708 KB Ok
8 Correct 7 ms 9708 KB Ok
9 Correct 7 ms 9708 KB Ok
10 Correct 8 ms 9708 KB Ok
11 Correct 8 ms 9708 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Ok
2 Correct 7 ms 9708 KB Ok
3 Correct 8 ms 9708 KB Ok
4 Correct 8 ms 9708 KB Ok
5 Correct 8 ms 9708 KB Ok
6 Correct 342 ms 31840 KB Ok
7 Correct 377 ms 35068 KB Ok
8 Correct 706 ms 37600 KB Ok
9 Correct 428 ms 34100 KB Ok
10 Correct 206 ms 23652 KB Ok
11 Correct 344 ms 36448 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9708 KB Ok
2 Correct 7 ms 9708 KB Ok
3 Correct 7 ms 9708 KB Ok
4 Correct 9 ms 9708 KB Ok
5 Correct 7 ms 9712 KB Ok
6 Correct 7 ms 9708 KB Ok
7 Correct 7 ms 9708 KB Ok
8 Correct 7 ms 9708 KB Ok
9 Correct 7 ms 9708 KB Ok
10 Correct 7 ms 9708 KB Ok
11 Correct 8 ms 9708 KB Ok
12 Correct 7 ms 9708 KB Ok
13 Correct 7 ms 9836 KB Ok
14 Correct 7 ms 9708 KB Ok
15 Correct 9 ms 9708 KB Ok
16 Correct 8 ms 9836 KB Ok
17 Correct 7 ms 9708 KB Ok
18 Correct 8 ms 9708 KB Ok
19 Correct 8 ms 9708 KB Ok
20 Correct 7 ms 9708 KB Ok
21 Correct 7 ms 9708 KB Ok
22 Correct 8 ms 9708 KB Ok
23 Correct 8 ms 9708 KB Ok
24 Correct 10 ms 9996 KB Ok
25 Correct 11 ms 9964 KB Ok
26 Correct 10 ms 9964 KB Ok
27 Correct 14 ms 9964 KB Ok
28 Correct 9 ms 9964 KB Ok
29 Correct 11 ms 9964 KB Ok
30 Correct 10 ms 9924 KB Ok
31 Correct 10 ms 9964 KB Ok
32 Correct 11 ms 9964 KB Ok
33 Correct 10 ms 9964 KB Ok
34 Correct 17 ms 10348 KB Ok
35 Correct 22 ms 10348 KB Ok
36 Correct 15 ms 10348 KB Ok
37 Correct 18 ms 10348 KB Ok
38 Correct 17 ms 10496 KB Ok
39 Correct 22 ms 10348 KB Ok
40 Correct 25 ms 10348 KB Ok
41 Correct 15 ms 10348 KB Ok
42 Correct 17 ms 10348 KB Ok
43 Correct 16 ms 10348 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9708 KB Ok
2 Correct 7 ms 9708 KB Ok
3 Correct 7 ms 9708 KB Ok
4 Correct 9 ms 9708 KB Ok
5 Correct 7 ms 9712 KB Ok
6 Correct 7 ms 9708 KB Ok
7 Correct 7 ms 9708 KB Ok
8 Correct 7 ms 9708 KB Ok
9 Correct 7 ms 9708 KB Ok
10 Correct 7 ms 9708 KB Ok
11 Correct 8 ms 9708 KB Ok
12 Correct 7 ms 9708 KB Ok
13 Correct 8 ms 9708 KB Ok
14 Correct 8 ms 9708 KB Ok
15 Correct 9 ms 9708 KB Ok
16 Correct 8 ms 9708 KB Ok
17 Correct 7 ms 9708 KB Ok
18 Correct 12 ms 9964 KB Ok
19 Correct 26 ms 11244 KB Ok
20 Correct 15 ms 10368 KB Ok
21 Correct 28 ms 11364 KB Ok
22 Correct 19 ms 10732 KB Ok
23 Correct 7 ms 9836 KB Ok
24 Correct 7 ms 9708 KB Ok
25 Correct 9 ms 9708 KB Ok
26 Correct 8 ms 9836 KB Ok
27 Correct 7 ms 9708 KB Ok
28 Correct 8 ms 9708 KB Ok
29 Correct 8 ms 9708 KB Ok
30 Correct 7 ms 9708 KB Ok
31 Correct 7 ms 9708 KB Ok
32 Correct 8 ms 9708 KB Ok
33 Correct 8 ms 9708 KB Ok
34 Correct 10 ms 9996 KB Ok
35 Correct 11 ms 9964 KB Ok
36 Correct 10 ms 9964 KB Ok
37 Correct 14 ms 9964 KB Ok
38 Correct 9 ms 9964 KB Ok
39 Correct 11 ms 9964 KB Ok
40 Correct 10 ms 9924 KB Ok
41 Correct 10 ms 9964 KB Ok
42 Correct 11 ms 9964 KB Ok
43 Correct 10 ms 9964 KB Ok
44 Correct 17 ms 10348 KB Ok
45 Correct 22 ms 10348 KB Ok
46 Correct 15 ms 10348 KB Ok
47 Correct 18 ms 10348 KB Ok
48 Correct 17 ms 10496 KB Ok
49 Correct 22 ms 10348 KB Ok
50 Correct 25 ms 10348 KB Ok
51 Correct 15 ms 10348 KB Ok
52 Correct 17 ms 10348 KB Ok
53 Correct 16 ms 10348 KB Ok
54 Correct 161 ms 16460 KB Ok
55 Correct 186 ms 16744 KB Ok
56 Correct 175 ms 16956 KB Ok
57 Correct 120 ms 15724 KB Ok
58 Correct 157 ms 16360 KB Ok
59 Correct 145 ms 15848 KB Ok
60 Correct 123 ms 15512 KB Ok
61 Correct 124 ms 16168 KB Ok
62 Correct 187 ms 16612 KB Ok
63 Correct 130 ms 15864 KB Ok
64 Correct 174 ms 16744 KB Ok
65 Correct 162 ms 16452 KB Ok
66 Correct 158 ms 16232 KB Ok
67 Correct 115 ms 15976 KB Ok
68 Correct 150 ms 16356 KB Ok
69 Correct 724 ms 27668 KB Ok
70 Correct 973 ms 28260 KB Ok
71 Correct 636 ms 27748 KB Ok
72 Correct 729 ms 27492 KB Ok
73 Correct 776 ms 27632 KB Ok
74 Correct 564 ms 27468 KB Ok
75 Correct 488 ms 27108 KB Ok
76 Correct 875 ms 28004 KB Ok
77 Correct 477 ms 27108 KB Ok
78 Correct 737 ms 27580 KB Ok
79 Correct 759 ms 27876 KB Ok
80 Correct 566 ms 27848 KB Ok
81 Correct 604 ms 27748 KB Ok
82 Correct 608 ms 27876 KB Ok
83 Correct 537 ms 27364 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9708 KB Ok
2 Correct 7 ms 9708 KB Ok
3 Correct 7 ms 9708 KB Ok
4 Correct 9 ms 9708 KB Ok
5 Correct 7 ms 9712 KB Ok
6 Correct 7 ms 9708 KB Ok
7 Correct 7 ms 9708 KB Ok
8 Correct 7 ms 9708 KB Ok
9 Correct 7 ms 9708 KB Ok
10 Correct 7 ms 9708 KB Ok
11 Correct 8 ms 9708 KB Ok
12 Correct 7 ms 9708 KB Ok
13 Correct 8 ms 9708 KB Ok
14 Correct 8 ms 9708 KB Ok
15 Correct 9 ms 9708 KB Ok
16 Correct 8 ms 9708 KB Ok
17 Correct 7 ms 9708 KB Ok
18 Correct 12 ms 9964 KB Ok
19 Correct 26 ms 11244 KB Ok
20 Correct 15 ms 10368 KB Ok
21 Correct 28 ms 11364 KB Ok
22 Correct 19 ms 10732 KB Ok
23 Correct 7 ms 9836 KB Ok
24 Correct 7 ms 9708 KB Ok
25 Correct 9 ms 9708 KB Ok
26 Correct 8 ms 9836 KB Ok
27 Correct 7 ms 9708 KB Ok
28 Correct 8 ms 9708 KB Ok
29 Correct 8 ms 9708 KB Ok
30 Correct 7 ms 9708 KB Ok
31 Correct 7 ms 9708 KB Ok
32 Correct 8 ms 9708 KB Ok
33 Correct 8 ms 9708 KB Ok
34 Correct 7 ms 9708 KB Ok
35 Correct 7 ms 9708 KB Ok
36 Correct 8 ms 9708 KB Ok
37 Correct 8 ms 9708 KB Ok
38 Correct 8 ms 9708 KB Ok
39 Correct 342 ms 31840 KB Ok
40 Correct 377 ms 35068 KB Ok
41 Correct 706 ms 37600 KB Ok
42 Correct 428 ms 34100 KB Ok
43 Correct 206 ms 23652 KB Ok
44 Correct 344 ms 36448 KB Ok
45 Correct 10 ms 9996 KB Ok
46 Correct 11 ms 9964 KB Ok
47 Correct 10 ms 9964 KB Ok
48 Correct 14 ms 9964 KB Ok
49 Correct 9 ms 9964 KB Ok
50 Correct 11 ms 9964 KB Ok
51 Correct 10 ms 9924 KB Ok
52 Correct 10 ms 9964 KB Ok
53 Correct 11 ms 9964 KB Ok
54 Correct 10 ms 9964 KB Ok
55 Correct 17 ms 10348 KB Ok
56 Correct 22 ms 10348 KB Ok
57 Correct 15 ms 10348 KB Ok
58 Correct 18 ms 10348 KB Ok
59 Correct 17 ms 10496 KB Ok
60 Correct 22 ms 10348 KB Ok
61 Correct 25 ms 10348 KB Ok
62 Correct 15 ms 10348 KB Ok
63 Correct 17 ms 10348 KB Ok
64 Correct 16 ms 10348 KB Ok
65 Correct 161 ms 16460 KB Ok
66 Correct 186 ms 16744 KB Ok
67 Correct 175 ms 16956 KB Ok
68 Correct 120 ms 15724 KB Ok
69 Correct 157 ms 16360 KB Ok
70 Correct 145 ms 15848 KB Ok
71 Correct 123 ms 15512 KB Ok
72 Correct 124 ms 16168 KB Ok
73 Correct 187 ms 16612 KB Ok
74 Correct 130 ms 15864 KB Ok
75 Correct 174 ms 16744 KB Ok
76 Correct 162 ms 16452 KB Ok
77 Correct 158 ms 16232 KB Ok
78 Correct 115 ms 15976 KB Ok
79 Correct 150 ms 16356 KB Ok
80 Correct 724 ms 27668 KB Ok
81 Correct 973 ms 28260 KB Ok
82 Correct 636 ms 27748 KB Ok
83 Correct 729 ms 27492 KB Ok
84 Correct 776 ms 27632 KB Ok
85 Correct 564 ms 27468 KB Ok
86 Correct 488 ms 27108 KB Ok
87 Correct 875 ms 28004 KB Ok
88 Correct 477 ms 27108 KB Ok
89 Correct 737 ms 27580 KB Ok
90 Correct 759 ms 27876 KB Ok
91 Correct 566 ms 27848 KB Ok
92 Correct 604 ms 27748 KB Ok
93 Correct 608 ms 27876 KB Ok
94 Correct 537 ms 27364 KB Ok
95 Correct 323 ms 27620 KB Ok
96 Correct 622 ms 35460 KB Ok
97 Correct 627 ms 30960 KB Ok
98 Correct 364 ms 30940 KB Ok
99 Correct 490 ms 30560 KB Ok
100 Correct 572 ms 29416 KB Ok
101 Correct 566 ms 32992 KB Ok
102 Correct 490 ms 30536 KB Ok
103 Correct 510 ms 32100 KB Ok
104 Correct 653 ms 34044 KB Ok
105 Correct 637 ms 34684 KB Ok
106 Correct 450 ms 35172 KB Ok
107 Correct 537 ms 33632 KB Ok
108 Correct 645 ms 34660 KB Ok
109 Correct 563 ms 36472 KB Ok
110 Execution timed out 2088 ms 67780 KB Time limit exceeded
111 Halted 0 ms 0 KB -