oj.uz

Submission #338118

# Submission time Handle Problem Language Result Execution time Memory
338118 2020-12-22T14:11:19 Z BeanZ Nice sequence (IZhO18_sequence) C++14
76 / 100
 672 ms 57824 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;
    if (u >= m && vis[u - m] == 0) dfs(u - m, mid);
    if ((u + n) <= mid && vis[u + n] == 0) dfs(u + n, 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 u = 0; u <= mid; u++){
        if (u >= m && id[u] < id[u - m]) return false;
        if ((u + n) <= mid && id[u] < id[u + n]) 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++){
            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:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 0; i < topo.size(); i++){
      |                     ~~^~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   42 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:43:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   43 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 56292 KB Ok
2 Correct 144 ms 56292 KB Ok
3 Correct 140 ms 53476 KB Ok
4 Correct 140 ms 53796 KB Ok
5 Correct 137 ms 53476 KB Ok
6 Correct 150 ms 54116 KB Ok
7 Correct 141 ms 53432 KB Ok
8 Correct 139 ms 53988 KB Ok
9 Correct 142 ms 53604 KB Ok
10 Correct 140 ms 54756 KB Ok
11 Correct 139 ms 53424 KB Ok
12 Correct 140 ms 53320 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 56292 KB Ok
2 Correct 151 ms 56292 KB Ok
3 Correct 145 ms 56292 KB Ok
4 Correct 142 ms 56292 KB Ok
5 Correct 146 ms 56308 KB Ok
6 Correct 147 ms 56292 KB Ok
7 Correct 161 ms 55652 KB Ok
8 Correct 155 ms 56292 KB Ok
9 Correct 167 ms 55652 KB Ok
10 Correct 169 ms 56444 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 37604 KB Ok
2 Correct 145 ms 56292 KB Ok
3 Correct 148 ms 56292 KB Ok
4 Correct 149 ms 56292 KB Ok
5 Correct 149 ms 56292 KB Ok
6 Correct 150 ms 56420 KB Ok
7 Correct 144 ms 56420 KB Ok
8 Correct 153 ms 56548 KB Ok
9 Correct 150 ms 56292 KB Ok
10 Correct 150 ms 56292 KB Ok
11 Correct 147 ms 56292 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 56292 KB Ok
2 Correct 159 ms 56420 KB Ok
3 Correct 156 ms 56292 KB Ok
4 Correct 152 ms 56292 KB Ok
5 Correct 152 ms 56312 KB Ok
6 Correct 426 ms 56288 KB Ok
7 Correct 415 ms 57824 KB Ok
8 Correct 672 ms 55392 KB Ok
9 Correct 503 ms 57568 KB Ok
10 Correct 339 ms 54112 KB Ok
11 Correct 449 ms 55264 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 56292 KB Ok
2 Correct 144 ms 56292 KB Ok
3 Correct 140 ms 53476 KB Ok
4 Correct 140 ms 53796 KB Ok
5 Correct 137 ms 53476 KB Ok
6 Correct 150 ms 54116 KB Ok
7 Correct 141 ms 53432 KB Ok
8 Correct 139 ms 53988 KB Ok
9 Correct 142 ms 53604 KB Ok
10 Correct 140 ms 54756 KB Ok
11 Correct 139 ms 53424 KB Ok
12 Correct 140 ms 53320 KB Ok
13 Correct 70 ms 37604 KB Ok
14 Correct 145 ms 56292 KB Ok
15 Correct 148 ms 56292 KB Ok
16 Correct 149 ms 56292 KB Ok
17 Correct 149 ms 56292 KB Ok
18 Correct 150 ms 56420 KB Ok
19 Correct 144 ms 56420 KB Ok
20 Correct 153 ms 56548 KB Ok
21 Correct 150 ms 56292 KB Ok
22 Correct 150 ms 56292 KB Ok
23 Correct 147 ms 56292 KB Ok
24 Correct 150 ms 53092 KB Ok
25 Correct 149 ms 53220 KB Ok
26 Correct 147 ms 53348 KB Ok
27 Correct 147 ms 53348 KB Ok
28 Correct 146 ms 53220 KB Ok
29 Correct 144 ms 54244 KB Ok
30 Correct 145 ms 53220 KB Ok
31 Correct 147 ms 53164 KB Ok
32 Correct 146 ms 53092 KB Ok
33 Correct 150 ms 53348 KB Ok
34 Correct 160 ms 56164 KB Ok
35 Correct 160 ms 56292 KB Ok
36 Correct 158 ms 56164 KB Ok
37 Correct 161 ms 56292 KB Ok
38 Correct 159 ms 56292 KB Ok
39 Correct 158 ms 56292 KB Ok
40 Correct 162 ms 56292 KB Ok
41 Correct 161 ms 56292 KB Ok
42 Correct 197 ms 56312 KB Ok
43 Correct 163 ms 56292 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 56292 KB Ok
2 Correct 144 ms 56292 KB Ok
3 Correct 140 ms 53476 KB Ok
4 Correct 140 ms 53796 KB Ok
5 Correct 137 ms 53476 KB Ok
6 Correct 150 ms 54116 KB Ok
7 Correct 141 ms 53432 KB Ok
8 Correct 139 ms 53988 KB Ok
9 Correct 142 ms 53604 KB Ok
10 Correct 140 ms 54756 KB Ok
11 Correct 139 ms 53424 KB Ok
12 Correct 140 ms 53320 KB Ok
13 Correct 149 ms 56292 KB Ok
14 Correct 151 ms 56292 KB Ok
15 Correct 145 ms 56292 KB Ok
16 Correct 142 ms 56292 KB Ok
17 Correct 146 ms 56308 KB Ok
18 Correct 147 ms 56292 KB Ok
19 Correct 161 ms 55652 KB Ok
20 Correct 155 ms 56292 KB Ok
21 Correct 167 ms 55652 KB Ok
22 Correct 169 ms 56444 KB Ok
23 Correct 70 ms 37604 KB Ok
24 Correct 145 ms 56292 KB Ok
25 Correct 148 ms 56292 KB Ok
26 Correct 149 ms 56292 KB Ok
27 Correct 149 ms 56292 KB Ok
28 Correct 150 ms 56420 KB Ok
29 Correct 144 ms 56420 KB Ok
30 Correct 153 ms 56548 KB Ok
31 Correct 150 ms 56292 KB Ok
32 Correct 150 ms 56292 KB Ok
33 Correct 147 ms 56292 KB Ok
34 Correct 150 ms 53092 KB Ok
35 Correct 149 ms 53220 KB Ok
36 Correct 147 ms 53348 KB Ok
37 Correct 147 ms 53348 KB Ok
38 Correct 146 ms 53220 KB Ok
39 Correct 144 ms 54244 KB Ok
40 Correct 145 ms 53220 KB Ok
41 Correct 147 ms 53164 KB Ok
42 Correct 146 ms 53092 KB Ok
43 Correct 150 ms 53348 KB Ok
44 Correct 160 ms 56164 KB Ok
45 Correct 160 ms 56292 KB Ok
46 Correct 158 ms 56164 KB Ok
47 Correct 161 ms 56292 KB Ok
48 Correct 159 ms 56292 KB Ok
49 Correct 158 ms 56292 KB Ok
50 Correct 162 ms 56292 KB Ok
51 Correct 161 ms 56292 KB Ok
52 Correct 197 ms 56312 KB Ok
53 Correct 163 ms 56292 KB Ok
54 Correct 313 ms 49252 KB Ok
55 Correct 353 ms 49508 KB Ok
56 Correct 351 ms 49764 KB Ok
57 Correct 278 ms 49508 KB Ok
58 Correct 310 ms 48996 KB Ok
59 Correct 290 ms 48996 KB Ok
60 Correct 273 ms 48868 KB Ok
61 Correct 281 ms 49512 KB Ok
62 Correct 337 ms 49252 KB Ok
63 Correct 292 ms 49380 KB Ok
64 Correct 341 ms 49636 KB Ok
65 Correct 318 ms 49124 KB Ok
66 Correct 300 ms 49316 KB Ok
67 Correct 282 ms 49488 KB Ok
68 Correct 298 ms 49764 KB Ok
69 Correct 503 ms 56180 KB Ok
70 Correct 514 ms 56736 KB Ok
71 Correct 486 ms 56292 KB Ok
72 Correct 509 ms 56036 KB Ok
73 Correct 483 ms 56292 KB Ok
74 Correct 491 ms 56036 KB Ok
75 Correct 511 ms 55652 KB Ok
76 Correct 512 ms 56420 KB Ok
77 Correct 489 ms 55588 KB Ok
78 Correct 509 ms 56292 KB Ok
79 Correct 502 ms 56280 KB Ok
80 Correct 496 ms 56548 KB Ok
81 Correct 524 ms 56336 KB Ok
82 Correct 485 ms 56292 KB Ok
83 Correct 485 ms 55780 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 56292 KB Ok
2 Correct 144 ms 56292 KB Ok
3 Correct 140 ms 53476 KB Ok
4 Correct 140 ms 53796 KB Ok
5 Correct 137 ms 53476 KB Ok
6 Correct 150 ms 54116 KB Ok
7 Correct 141 ms 53432 KB Ok
8 Correct 139 ms 53988 KB Ok
9 Correct 142 ms 53604 KB Ok
10 Correct 140 ms 54756 KB Ok
11 Correct 139 ms 53424 KB Ok
12 Correct 140 ms 53320 KB Ok
13 Correct 149 ms 56292 KB Ok
14 Correct 151 ms 56292 KB Ok
15 Correct 145 ms 56292 KB Ok
16 Correct 142 ms 56292 KB Ok
17 Correct 146 ms 56308 KB Ok
18 Correct 147 ms 56292 KB Ok
19 Correct 161 ms 55652 KB Ok
20 Correct 155 ms 56292 KB Ok
21 Correct 167 ms 55652 KB Ok
22 Correct 169 ms 56444 KB Ok
23 Correct 70 ms 37604 KB Ok
24 Correct 145 ms 56292 KB Ok
25 Correct 148 ms 56292 KB Ok
26 Correct 149 ms 56292 KB Ok
27 Correct 149 ms 56292 KB Ok
28 Correct 150 ms 56420 KB Ok
29 Correct 144 ms 56420 KB Ok
30 Correct 153 ms 56548 KB Ok
31 Correct 150 ms 56292 KB Ok
32 Correct 150 ms 56292 KB Ok
33 Correct 147 ms 56292 KB Ok
34 Correct 151 ms 56292 KB Ok
35 Correct 159 ms 56420 KB Ok
36 Correct 156 ms 56292 KB Ok
37 Correct 152 ms 56292 KB Ok
38 Correct 152 ms 56312 KB Ok
39 Correct 426 ms 56288 KB Ok
40 Correct 415 ms 57824 KB Ok
41 Correct 672 ms 55392 KB Ok
42 Correct 503 ms 57568 KB Ok
43 Correct 339 ms 54112 KB Ok
44 Correct 449 ms 55264 KB Ok
45 Correct 150 ms 53092 KB Ok
46 Correct 149 ms 53220 KB Ok
47 Correct 147 ms 53348 KB Ok
48 Correct 147 ms 53348 KB Ok
49 Correct 146 ms 53220 KB Ok
50 Correct 144 ms 54244 KB Ok
51 Correct 145 ms 53220 KB Ok
52 Correct 147 ms 53164 KB Ok
53 Correct 146 ms 53092 KB Ok
54 Correct 150 ms 53348 KB Ok
55 Correct 160 ms 56164 KB Ok
56 Correct 160 ms 56292 KB Ok
57 Correct 158 ms 56164 KB Ok
58 Correct 161 ms 56292 KB Ok
59 Correct 159 ms 56292 KB Ok
60 Correct 158 ms 56292 KB Ok
61 Correct 162 ms 56292 KB Ok
62 Correct 161 ms 56292 KB Ok
63 Correct 197 ms 56312 KB Ok
64 Correct 163 ms 56292 KB Ok
65 Correct 313 ms 49252 KB Ok
66 Correct 353 ms 49508 KB Ok
67 Correct 351 ms 49764 KB Ok
68 Correct 278 ms 49508 KB Ok
69 Correct 310 ms 48996 KB Ok
70 Correct 290 ms 48996 KB Ok
71 Correct 273 ms 48868 KB Ok
72 Correct 281 ms 49512 KB Ok
73 Correct 337 ms 49252 KB Ok
74 Correct 292 ms 49380 KB Ok
75 Correct 341 ms 49636 KB Ok
76 Correct 318 ms 49124 KB Ok
77 Correct 300 ms 49316 KB Ok
78 Correct 282 ms 49488 KB Ok
79 Correct 298 ms 49764 KB Ok
80 Correct 503 ms 56180 KB Ok
81 Correct 514 ms 56736 KB Ok
82 Correct 486 ms 56292 KB Ok
83 Correct 509 ms 56036 KB Ok
84 Correct 483 ms 56292 KB Ok
85 Correct 491 ms 56036 KB Ok
86 Correct 511 ms 55652 KB Ok
87 Correct 512 ms 56420 KB Ok
88 Correct 489 ms 55588 KB Ok
89 Correct 509 ms 56292 KB Ok
90 Correct 502 ms 56280 KB Ok
91 Correct 496 ms 56548 KB Ok
92 Correct 524 ms 56336 KB Ok
93 Correct 485 ms 56292 KB Ok
94 Correct 485 ms 55780 KB Ok
95 Incorrect 515 ms 43104 KB Jury has the better answer : jans = 239234, pans = 200001
96 Halted 0 ms 0 KB -