oj.uz

Submission #338110

# Submission time Handle Problem Language Result Execution time Memory
338110 2020-12-22T14:00:00 Z BeanZ Nice sequence (IZhO18_sequence) C++14
58 / 100
 2000 ms 46944 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){
    vis[u] = 1;
    for (auto j : node[u]){
        if (vis[j]) continue;
        dfs(j);
    }
    topo.push_back(u);
}
bool chk(ll mid){
    for (int i = 0; i <= mid; i++) node[i].clear(), vis[i] = 0;
    for (int i = 0; i <= mid; i++){
        if (i >= n) node[i - n].push_back(i);
        if (i >= m) node[i].push_back(i - m);
    }
    topo.clear();
    for (int i = 0; i <= mid; i++){
        if (vis[i]) continue;
        dfs(i);
    }
    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 (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;
        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:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i = 0; i < topo.size(); i++){
      |                     ~~^~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   49 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:50:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   50 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 32996 KB Ok
2 Correct 109 ms 32996 KB Ok
3 Correct 107 ms 28644 KB Ok
4 Correct 106 ms 28900 KB Ok
5 Correct 108 ms 28644 KB Ok
6 Correct 109 ms 29412 KB Ok
7 Correct 109 ms 28516 KB Ok
8 Correct 107 ms 29412 KB Ok
9 Correct 109 ms 28596 KB Ok
10 Correct 108 ms 30620 KB Ok
11 Correct 106 ms 28516 KB Ok
12 Correct 101 ms 28388 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 32996 KB Ok
2 Correct 126 ms 33016 KB Ok
3 Correct 112 ms 32932 KB Ok
4 Correct 112 ms 32996 KB Ok
5 Correct 106 ms 32996 KB Ok
6 Correct 110 ms 32996 KB Ok
7 Correct 128 ms 33252 KB Ok
8 Correct 113 ms 33124 KB Ok
9 Correct 136 ms 33508 KB Ok
10 Correct 121 ms 33124 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 32996 KB Ok
2 Correct 110 ms 32996 KB Ok
3 Correct 96 ms 33128 KB Ok
4 Correct 99 ms 32996 KB Ok
5 Correct 98 ms 32996 KB Ok
6 Correct 109 ms 32996 KB Ok
7 Correct 105 ms 32996 KB Ok
8 Correct 102 ms 32996 KB Ok
9 Correct 102 ms 32996 KB Ok
10 Correct 103 ms 32996 KB Ok
11 Correct 108 ms 32996 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 32996 KB Ok
2 Correct 107 ms 32996 KB Ok
3 Correct 108 ms 32996 KB Ok
4 Correct 116 ms 32996 KB Ok
5 Correct 110 ms 32996 KB Ok
6 Correct 725 ms 41828 KB Ok
7 Correct 564 ms 43964 KB Ok
8 Correct 1145 ms 46944 KB Ok
9 Correct 752 ms 43872 KB Ok
10 Correct 429 ms 36448 KB Ok
11 Correct 703 ms 45152 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 32996 KB Ok
2 Correct 109 ms 32996 KB Ok
3 Correct 107 ms 28644 KB Ok
4 Correct 106 ms 28900 KB Ok
5 Correct 108 ms 28644 KB Ok
6 Correct 109 ms 29412 KB Ok
7 Correct 109 ms 28516 KB Ok
8 Correct 107 ms 29412 KB Ok
9 Correct 109 ms 28596 KB Ok
10 Correct 108 ms 30620 KB Ok
11 Correct 106 ms 28516 KB Ok
12 Correct 101 ms 28388 KB Ok
13 Correct 50 ms 32996 KB Ok
14 Correct 110 ms 32996 KB Ok
15 Correct 96 ms 33128 KB Ok
16 Correct 99 ms 32996 KB Ok
17 Correct 98 ms 32996 KB Ok
18 Correct 109 ms 32996 KB Ok
19 Correct 105 ms 32996 KB Ok
20 Correct 102 ms 32996 KB Ok
21 Correct 102 ms 32996 KB Ok
22 Correct 103 ms 32996 KB Ok
23 Correct 108 ms 32996 KB Ok
24 Correct 118 ms 28260 KB Ok
25 Correct 126 ms 28388 KB Ok
26 Correct 124 ms 28644 KB Ok
27 Correct 127 ms 28644 KB Ok
28 Correct 121 ms 28388 KB Ok
29 Correct 130 ms 29796 KB Ok
30 Correct 124 ms 28516 KB Ok
31 Correct 144 ms 28388 KB Ok
32 Correct 124 ms 28388 KB Ok
33 Correct 128 ms 28516 KB Ok
34 Correct 249 ms 33124 KB Ok
35 Correct 171 ms 33124 KB Ok
36 Correct 196 ms 33124 KB Ok
37 Correct 191 ms 33124 KB Ok
38 Correct 175 ms 33124 KB Ok
39 Correct 210 ms 32976 KB Ok
40 Correct 183 ms 33124 KB Ok
41 Correct 174 ms 33124 KB Ok
42 Correct 239 ms 33124 KB Ok
43 Correct 169 ms 33252 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 32996 KB Ok
2 Correct 109 ms 32996 KB Ok
3 Correct 107 ms 28644 KB Ok
4 Correct 106 ms 28900 KB Ok
5 Correct 108 ms 28644 KB Ok
6 Correct 109 ms 29412 KB Ok
7 Correct 109 ms 28516 KB Ok
8 Correct 107 ms 29412 KB Ok
9 Correct 109 ms 28596 KB Ok
10 Correct 108 ms 30620 KB Ok
11 Correct 106 ms 28516 KB Ok
12 Correct 101 ms 28388 KB Ok
13 Correct 101 ms 32996 KB Ok
14 Correct 126 ms 33016 KB Ok
15 Correct 112 ms 32932 KB Ok
16 Correct 112 ms 32996 KB Ok
17 Correct 106 ms 32996 KB Ok
18 Correct 110 ms 32996 KB Ok
19 Correct 128 ms 33252 KB Ok
20 Correct 113 ms 33124 KB Ok
21 Correct 136 ms 33508 KB Ok
22 Correct 121 ms 33124 KB Ok
23 Correct 50 ms 32996 KB Ok
24 Correct 110 ms 32996 KB Ok
25 Correct 96 ms 33128 KB Ok
26 Correct 99 ms 32996 KB Ok
27 Correct 98 ms 32996 KB Ok
28 Correct 109 ms 32996 KB Ok
29 Correct 105 ms 32996 KB Ok
30 Correct 102 ms 32996 KB Ok
31 Correct 102 ms 32996 KB Ok
32 Correct 103 ms 32996 KB Ok
33 Correct 108 ms 32996 KB Ok
34 Correct 118 ms 28260 KB Ok
35 Correct 126 ms 28388 KB Ok
36 Correct 124 ms 28644 KB Ok
37 Correct 127 ms 28644 KB Ok
38 Correct 121 ms 28388 KB Ok
39 Correct 130 ms 29796 KB Ok
40 Correct 124 ms 28516 KB Ok
41 Correct 144 ms 28388 KB Ok
42 Correct 124 ms 28388 KB Ok
43 Correct 128 ms 28516 KB Ok
44 Correct 249 ms 33124 KB Ok
45 Correct 171 ms 33124 KB Ok
46 Correct 196 ms 33124 KB Ok
47 Correct 191 ms 33124 KB Ok
48 Correct 175 ms 33124 KB Ok
49 Correct 210 ms 32976 KB Ok
50 Correct 183 ms 33124 KB Ok
51 Correct 174 ms 33124 KB Ok
52 Correct 239 ms 33124 KB Ok
53 Correct 169 ms 33252 KB Ok
54 Correct 442 ms 29924 KB Ok
55 Correct 553 ms 30308 KB Ok
56 Correct 539 ms 30436 KB Ok
57 Correct 364 ms 29540 KB Ok
58 Correct 441 ms 29796 KB Ok
59 Correct 405 ms 29668 KB Ok
60 Correct 338 ms 29668 KB Ok
61 Correct 374 ms 29508 KB Ok
62 Correct 485 ms 30052 KB Ok
63 Correct 410 ms 29796 KB Ok
64 Correct 517 ms 30400 KB Ok
65 Correct 474 ms 29924 KB Ok
66 Correct 414 ms 29796 KB Ok
67 Correct 367 ms 29796 KB Ok
68 Correct 402 ms 29960 KB Ok
69 Correct 1864 ms 39164 KB Ok
70 Correct 1701 ms 39652 KB Ok
71 Correct 1700 ms 39088 KB Ok
72 Correct 1728 ms 39012 KB Ok
73 Correct 1431 ms 39268 KB Ok
74 Correct 1872 ms 38940 KB Ok
75 Correct 1707 ms 38568 KB Ok
76 Correct 1564 ms 39268 KB Ok
77 Correct 1785 ms 38500 KB Ok
78 Correct 1691 ms 39268 KB Ok
79 Correct 1664 ms 39168 KB Ok
80 Correct 1708 ms 39368 KB Ok
81 Execution timed out 2076 ms 38660 KB Time limit exceeded
82 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 32996 KB Ok
2 Correct 109 ms 32996 KB Ok
3 Correct 107 ms 28644 KB Ok
4 Correct 106 ms 28900 KB Ok
5 Correct 108 ms 28644 KB Ok
6 Correct 109 ms 29412 KB Ok
7 Correct 109 ms 28516 KB Ok
8 Correct 107 ms 29412 KB Ok
9 Correct 109 ms 28596 KB Ok
10 Correct 108 ms 30620 KB Ok
11 Correct 106 ms 28516 KB Ok
12 Correct 101 ms 28388 KB Ok
13 Correct 101 ms 32996 KB Ok
14 Correct 126 ms 33016 KB Ok
15 Correct 112 ms 32932 KB Ok
16 Correct 112 ms 32996 KB Ok
17 Correct 106 ms 32996 KB Ok
18 Correct 110 ms 32996 KB Ok
19 Correct 128 ms 33252 KB Ok
20 Correct 113 ms 33124 KB Ok
21 Correct 136 ms 33508 KB Ok
22 Correct 121 ms 33124 KB Ok
23 Correct 50 ms 32996 KB Ok
24 Correct 110 ms 32996 KB Ok
25 Correct 96 ms 33128 KB Ok
26 Correct 99 ms 32996 KB Ok
27 Correct 98 ms 32996 KB Ok
28 Correct 109 ms 32996 KB Ok
29 Correct 105 ms 32996 KB Ok
30 Correct 102 ms 32996 KB Ok
31 Correct 102 ms 32996 KB Ok
32 Correct 103 ms 32996 KB Ok
33 Correct 108 ms 32996 KB Ok
34 Correct 99 ms 32996 KB Ok
35 Correct 107 ms 32996 KB Ok
36 Correct 108 ms 32996 KB Ok
37 Correct 116 ms 32996 KB Ok
38 Correct 110 ms 32996 KB Ok
39 Correct 725 ms 41828 KB Ok
40 Correct 564 ms 43964 KB Ok
41 Correct 1145 ms 46944 KB Ok
42 Correct 752 ms 43872 KB Ok
43 Correct 429 ms 36448 KB Ok
44 Correct 703 ms 45152 KB Ok
45 Correct 118 ms 28260 KB Ok
46 Correct 126 ms 28388 KB Ok
47 Correct 124 ms 28644 KB Ok
48 Correct 127 ms 28644 KB Ok
49 Correct 121 ms 28388 KB Ok
50 Correct 130 ms 29796 KB Ok
51 Correct 124 ms 28516 KB Ok
52 Correct 144 ms 28388 KB Ok
53 Correct 124 ms 28388 KB Ok
54 Correct 128 ms 28516 KB Ok
55 Correct 249 ms 33124 KB Ok
56 Correct 171 ms 33124 KB Ok
57 Correct 196 ms 33124 KB Ok
58 Correct 191 ms 33124 KB Ok
59 Correct 175 ms 33124 KB Ok
60 Correct 210 ms 32976 KB Ok
61 Correct 183 ms 33124 KB Ok
62 Correct 174 ms 33124 KB Ok
63 Correct 239 ms 33124 KB Ok
64 Correct 169 ms 33252 KB Ok
65 Correct 442 ms 29924 KB Ok
66 Correct 553 ms 30308 KB Ok
67 Correct 539 ms 30436 KB Ok
68 Correct 364 ms 29540 KB Ok
69 Correct 441 ms 29796 KB Ok
70 Correct 405 ms 29668 KB Ok
71 Correct 338 ms 29668 KB Ok
72 Correct 374 ms 29508 KB Ok
73 Correct 485 ms 30052 KB Ok
74 Correct 410 ms 29796 KB Ok
75 Correct 517 ms 30400 KB Ok
76 Correct 474 ms 29924 KB Ok
77 Correct 414 ms 29796 KB Ok
78 Correct 367 ms 29796 KB Ok
79 Correct 402 ms 29960 KB Ok
80 Correct 1864 ms 39164 KB Ok
81 Correct 1701 ms 39652 KB Ok
82 Correct 1700 ms 39088 KB Ok
83 Correct 1728 ms 39012 KB Ok
84 Correct 1431 ms 39268 KB Ok
85 Correct 1872 ms 38940 KB Ok
86 Correct 1707 ms 38568 KB Ok
87 Correct 1564 ms 39268 KB Ok
88 Correct 1785 ms 38500 KB Ok
89 Correct 1691 ms 39268 KB Ok
90 Correct 1664 ms 39168 KB Ok
91 Correct 1708 ms 39368 KB Ok
92 Execution timed out 2076 ms 38660 KB Time limit exceeded
93 Halted 0 ms 0 KB -