oj.uz

Submission #338112

# Submission time Handle Problem Language Result Execution time Memory
338112 2020-12-22T14:04:31 Z BeanZ Nice sequence (IZhO18_sequence) C++14
58 / 100
 2000 ms 49632 KB 
// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define endl '\n'
const int N = 1e6 + 50;
long long mod = 1e9 + 7;
const int lim = 700;
const int lg = 18;
const int base = 311;
const long double eps = 1e-6;
ll n, m;
vector<ll> node[N];
vector<ll> topo;
ll vis[N], id[N];
void dfs(ll u, ll mid){
    vis[u] = 1;
    for (auto j : node[u]){
        if (vis[j] || j > mid) continue;
        dfs(j, mid);
    }
    topo.push_back(u);
}
bool chk(ll mid){
    for (int i = 0; i <= mid; i++) vis[i] = 0;
    topo.clear();
    for (int i = 0; i <= mid; i++){
        if (vis[i]) continue;
        dfs(i, mid);
    }
    for (int i = 0; i < topo.size(); i++){
        id[topo[i]] = i;
    }
    for (int i = 0; i <= mid; i++){
        for (auto j : node[i]){
            if (j > mid) continue;
            if (id[i] < id[j]) return false;
        }
    }
    return true;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("tests.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll t;
    cin >> t;
    while (t--){
        cin >> n >> m;
        ll l = 1, h = 2e5 + 1;
        for (int i = 0; i <= h; i++) node[i].clear();
        for (int i = 0; i <= h; i++){
            if (i >= n) node[i - n].push_back(i);
            if (i >= m) node[i].push_back(i - m);
        }
        while (l <= h){
            ll mid = (l + h) >> 1;
            if (chk(mid)) l = mid + 1;
            else h = mid - 1;
        }
        cout << h << endl;
        chk(h);
        for (int i = 1; i <= h; i++){
            cout << id[i] - id[i - 1] << " ";
        }
        cout << endl;
    }
}
/*
Ans:

Out:
*/

Compilation message

sequence.cpp: In function 'bool chk(int)':
sequence.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i = 0; i < topo.size(); i++){
      |                     ~~^~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   46 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   47 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 37744 KB Ok
2 Correct 125 ms 37604 KB Ok
3 Correct 119 ms 31952 KB Ok
4 Correct 121 ms 32228 KB Ok
5 Correct 122 ms 31844 KB Ok
6 Correct 126 ms 32996 KB Ok
7 Correct 153 ms 31716 KB Ok
8 Correct 131 ms 32996 KB Ok
9 Correct 118 ms 31844 KB Ok
10 Correct 118 ms 34532 KB Ok
11 Correct 122 ms 31716 KB Ok
12 Correct 126 ms 31588 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 37604 KB Ok
2 Correct 127 ms 37604 KB Ok
3 Correct 126 ms 37604 KB Ok
4 Correct 145 ms 37604 KB Ok
5 Correct 124 ms 37604 KB Ok
6 Correct 114 ms 37732 KB Ok
7 Correct 133 ms 37860 KB Ok
8 Correct 120 ms 37860 KB Ok
9 Correct 138 ms 38116 KB Ok
10 Correct 125 ms 37860 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 37604 KB Ok
2 Correct 112 ms 37604 KB Ok
3 Correct 118 ms 37604 KB Ok
4 Correct 116 ms 37604 KB Ok
5 Correct 116 ms 37604 KB Ok
6 Correct 117 ms 37604 KB Ok
7 Correct 107 ms 37604 KB Ok
8 Correct 118 ms 37604 KB Ok
9 Correct 129 ms 37604 KB Ok
10 Correct 114 ms 37604 KB Ok
11 Correct 119 ms 37604 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 37604 KB Ok
2 Correct 123 ms 37604 KB Ok
3 Correct 123 ms 37604 KB Ok
4 Correct 129 ms 37604 KB Ok
5 Correct 129 ms 37604 KB Ok
6 Correct 643 ms 45152 KB Ok
7 Correct 469 ms 47200 KB Ok
8 Correct 941 ms 49632 KB Ok
9 Correct 617 ms 47584 KB Ok
10 Correct 419 ms 39776 KB Ok
11 Correct 554 ms 48496 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 37744 KB Ok
2 Correct 125 ms 37604 KB Ok
3 Correct 119 ms 31952 KB Ok
4 Correct 121 ms 32228 KB Ok
5 Correct 122 ms 31844 KB Ok
6 Correct 126 ms 32996 KB Ok
7 Correct 153 ms 31716 KB Ok
8 Correct 131 ms 32996 KB Ok
9 Correct 118 ms 31844 KB Ok
10 Correct 118 ms 34532 KB Ok
11 Correct 122 ms 31716 KB Ok
12 Correct 126 ms 31588 KB Ok
13 Correct 58 ms 37604 KB Ok
14 Correct 112 ms 37604 KB Ok
15 Correct 118 ms 37604 KB Ok
16 Correct 116 ms 37604 KB Ok
17 Correct 116 ms 37604 KB Ok
18 Correct 117 ms 37604 KB Ok
19 Correct 107 ms 37604 KB Ok
20 Correct 118 ms 37604 KB Ok
21 Correct 129 ms 37604 KB Ok
22 Correct 114 ms 37604 KB Ok
23 Correct 119 ms 37604 KB Ok
24 Correct 126 ms 31492 KB Ok
25 Correct 139 ms 31716 KB Ok
26 Correct 135 ms 31972 KB Ok
27 Correct 140 ms 31932 KB Ok
28 Correct 135 ms 31716 KB Ok
29 Correct 154 ms 33612 KB Ok
30 Correct 138 ms 31844 KB Ok
31 Correct 144 ms 31588 KB Ok
32 Correct 139 ms 31588 KB Ok
33 Correct 140 ms 31852 KB Ok
34 Correct 282 ms 37732 KB Ok
35 Correct 209 ms 37860 KB Ok
36 Correct 258 ms 37732 KB Ok
37 Correct 198 ms 37732 KB Ok
38 Correct 215 ms 38012 KB Ok
39 Correct 244 ms 37860 KB Ok
40 Correct 219 ms 37860 KB Ok
41 Correct 199 ms 37800 KB Ok
42 Correct 268 ms 37732 KB Ok
43 Correct 204 ms 38116 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 37744 KB Ok
2 Correct 125 ms 37604 KB Ok
3 Correct 119 ms 31952 KB Ok
4 Correct 121 ms 32228 KB Ok
5 Correct 122 ms 31844 KB Ok
6 Correct 126 ms 32996 KB Ok
7 Correct 153 ms 31716 KB Ok
8 Correct 131 ms 32996 KB Ok
9 Correct 118 ms 31844 KB Ok
10 Correct 118 ms 34532 KB Ok
11 Correct 122 ms 31716 KB Ok
12 Correct 126 ms 31588 KB Ok
13 Correct 113 ms 37604 KB Ok
14 Correct 127 ms 37604 KB Ok
15 Correct 126 ms 37604 KB Ok
16 Correct 145 ms 37604 KB Ok
17 Correct 124 ms 37604 KB Ok
18 Correct 114 ms 37732 KB Ok
19 Correct 133 ms 37860 KB Ok
20 Correct 120 ms 37860 KB Ok
21 Correct 138 ms 38116 KB Ok
22 Correct 125 ms 37860 KB Ok
23 Correct 58 ms 37604 KB Ok
24 Correct 112 ms 37604 KB Ok
25 Correct 118 ms 37604 KB Ok
26 Correct 116 ms 37604 KB Ok
27 Correct 116 ms 37604 KB Ok
28 Correct 117 ms 37604 KB Ok
29 Correct 107 ms 37604 KB Ok
30 Correct 118 ms 37604 KB Ok
31 Correct 129 ms 37604 KB Ok
32 Correct 114 ms 37604 KB Ok
33 Correct 119 ms 37604 KB Ok
34 Correct 126 ms 31492 KB Ok
35 Correct 139 ms 31716 KB Ok
36 Correct 135 ms 31972 KB Ok
37 Correct 140 ms 31932 KB Ok
38 Correct 135 ms 31716 KB Ok
39 Correct 154 ms 33612 KB Ok
40 Correct 138 ms 31844 KB Ok
41 Correct 144 ms 31588 KB Ok
42 Correct 139 ms 31588 KB Ok
43 Correct 140 ms 31852 KB Ok
44 Correct 282 ms 37732 KB Ok
45 Correct 209 ms 37860 KB Ok
46 Correct 258 ms 37732 KB Ok
47 Correct 198 ms 37732 KB Ok
48 Correct 215 ms 38012 KB Ok
49 Correct 244 ms 37860 KB Ok
50 Correct 219 ms 37860 KB Ok
51 Correct 199 ms 37800 KB Ok
52 Correct 268 ms 37732 KB Ok
53 Correct 204 ms 38116 KB Ok
54 Correct 456 ms 33124 KB Ok
55 Correct 485 ms 33380 KB Ok
56 Correct 483 ms 33508 KB Ok
57 Correct 321 ms 32868 KB Ok
58 Correct 397 ms 33124 KB Ok
59 Correct 335 ms 32932 KB Ok
60 Correct 309 ms 32612 KB Ok
61 Correct 327 ms 32740 KB Ok
62 Correct 407 ms 33124 KB Ok
63 Correct 383 ms 32868 KB Ok
64 Correct 491 ms 33636 KB Ok
65 Correct 413 ms 32996 KB Ok
66 Correct 403 ms 32912 KB Ok
67 Correct 340 ms 32868 KB Ok
68 Correct 396 ms 33000 KB Ok
69 Execution timed out 2036 ms 43156 KB Time limit exceeded
70 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 37744 KB Ok
2 Correct 125 ms 37604 KB Ok
3 Correct 119 ms 31952 KB Ok
4 Correct 121 ms 32228 KB Ok
5 Correct 122 ms 31844 KB Ok
6 Correct 126 ms 32996 KB Ok
7 Correct 153 ms 31716 KB Ok
8 Correct 131 ms 32996 KB Ok
9 Correct 118 ms 31844 KB Ok
10 Correct 118 ms 34532 KB Ok
11 Correct 122 ms 31716 KB Ok
12 Correct 126 ms 31588 KB Ok
13 Correct 113 ms 37604 KB Ok
14 Correct 127 ms 37604 KB Ok
15 Correct 126 ms 37604 KB Ok
16 Correct 145 ms 37604 KB Ok
17 Correct 124 ms 37604 KB Ok
18 Correct 114 ms 37732 KB Ok
19 Correct 133 ms 37860 KB Ok
20 Correct 120 ms 37860 KB Ok
21 Correct 138 ms 38116 KB Ok
22 Correct 125 ms 37860 KB Ok
23 Correct 58 ms 37604 KB Ok
24 Correct 112 ms 37604 KB Ok
25 Correct 118 ms 37604 KB Ok
26 Correct 116 ms 37604 KB Ok
27 Correct 116 ms 37604 KB Ok
28 Correct 117 ms 37604 KB Ok
29 Correct 107 ms 37604 KB Ok
30 Correct 118 ms 37604 KB Ok
31 Correct 129 ms 37604 KB Ok
32 Correct 114 ms 37604 KB Ok
33 Correct 119 ms 37604 KB Ok
34 Correct 111 ms 37604 KB Ok
35 Correct 123 ms 37604 KB Ok
36 Correct 123 ms 37604 KB Ok
37 Correct 129 ms 37604 KB Ok
38 Correct 129 ms 37604 KB Ok
39 Correct 643 ms 45152 KB Ok
40 Correct 469 ms 47200 KB Ok
41 Correct 941 ms 49632 KB Ok
42 Correct 617 ms 47584 KB Ok
43 Correct 419 ms 39776 KB Ok
44 Correct 554 ms 48496 KB Ok
45 Correct 126 ms 31492 KB Ok
46 Correct 139 ms 31716 KB Ok
47 Correct 135 ms 31972 KB Ok
48 Correct 140 ms 31932 KB Ok
49 Correct 135 ms 31716 KB Ok
50 Correct 154 ms 33612 KB Ok
51 Correct 138 ms 31844 KB Ok
52 Correct 144 ms 31588 KB Ok
53 Correct 139 ms 31588 KB Ok
54 Correct 140 ms 31852 KB Ok
55 Correct 282 ms 37732 KB Ok
56 Correct 209 ms 37860 KB Ok
57 Correct 258 ms 37732 KB Ok
58 Correct 198 ms 37732 KB Ok
59 Correct 215 ms 38012 KB Ok
60 Correct 244 ms 37860 KB Ok
61 Correct 219 ms 37860 KB Ok
62 Correct 199 ms 37800 KB Ok
63 Correct 268 ms 37732 KB Ok
64 Correct 204 ms 38116 KB Ok
65 Correct 456 ms 33124 KB Ok
66 Correct 485 ms 33380 KB Ok
67 Correct 483 ms 33508 KB Ok
68 Correct 321 ms 32868 KB Ok
69 Correct 397 ms 33124 KB Ok
70 Correct 335 ms 32932 KB Ok
71 Correct 309 ms 32612 KB Ok
72 Correct 327 ms 32740 KB Ok
73 Correct 407 ms 33124 KB Ok
74 Correct 383 ms 32868 KB Ok
75 Correct 491 ms 33636 KB Ok
76 Correct 413 ms 32996 KB Ok
77 Correct 403 ms 32912 KB Ok
78 Correct 340 ms 32868 KB Ok
79 Correct 396 ms 33000 KB Ok
80 Execution timed out 2036 ms 43156 KB Time limit exceeded
81 Halted 0 ms 0 KB -