oj.uz

Submission #338109

# Submission time Handle Problem Language Result Execution time Memory
338109 2020-12-22T13:58:48 Z BeanZ Nice sequence (IZhO18_sequence) C++14
58 / 100
 2000 ms 49760 KB 
// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#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 = 4e5;
        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(long long int)':
sequence.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long 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 198 ms 44252 KB Ok
2 Correct 219 ms 44252 KB Ok
3 Correct 220 ms 35620 KB Ok
4 Correct 227 ms 36316 KB Ok
5 Correct 243 ms 35676 KB Ok
6 Correct 239 ms 37212 KB Ok
7 Correct 241 ms 35548 KB Ok
8 Correct 240 ms 37212 KB Ok
9 Correct 223 ms 35548 KB Ok
10 Correct 223 ms 39644 KB Ok
11 Correct 255 ms 35420 KB Ok
12 Correct 206 ms 35256 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 44252 KB Ok
2 Correct 242 ms 44252 KB Ok
3 Correct 224 ms 44408 KB Ok
4 Correct 228 ms 44380 KB Ok
5 Correct 258 ms 44412 KB Ok
6 Correct 197 ms 44380 KB Ok
7 Correct 210 ms 44636 KB Ok
8 Correct 201 ms 44636 KB Ok
9 Correct 220 ms 44756 KB Ok
10 Correct 211 ms 44636 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 44252 KB Ok
2 Correct 194 ms 44252 KB Ok
3 Correct 188 ms 44252 KB Ok
4 Correct 196 ms 44252 KB Ok
5 Correct 202 ms 44380 KB Ok
6 Correct 197 ms 44276 KB Ok
7 Correct 196 ms 44380 KB Ok
8 Correct 204 ms 44252 KB Ok
9 Correct 198 ms 44252 KB Ok
10 Correct 207 ms 44252 KB Ok
11 Correct 222 ms 44380 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 44252 KB Ok
2 Correct 213 ms 44252 KB Ok
3 Correct 227 ms 44380 KB Ok
4 Correct 244 ms 44252 KB Ok
5 Correct 240 ms 44252 KB Ok
6 Correct 804 ms 47828 KB Ok
7 Correct 628 ms 46428 KB Ok
8 Correct 1233 ms 49760 KB Ok
9 Correct 784 ms 48732 KB Ok
10 Correct 511 ms 45660 KB Ok
11 Correct 698 ms 47964 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 44252 KB Ok
2 Correct 219 ms 44252 KB Ok
3 Correct 220 ms 35620 KB Ok
4 Correct 227 ms 36316 KB Ok
5 Correct 243 ms 35676 KB Ok
6 Correct 239 ms 37212 KB Ok
7 Correct 241 ms 35548 KB Ok
8 Correct 240 ms 37212 KB Ok
9 Correct 223 ms 35548 KB Ok
10 Correct 223 ms 39644 KB Ok
11 Correct 255 ms 35420 KB Ok
12 Correct 206 ms 35256 KB Ok
13 Correct 85 ms 44252 KB Ok
14 Correct 194 ms 44252 KB Ok
15 Correct 188 ms 44252 KB Ok
16 Correct 196 ms 44252 KB Ok
17 Correct 202 ms 44380 KB Ok
18 Correct 197 ms 44276 KB Ok
19 Correct 196 ms 44380 KB Ok
20 Correct 204 ms 44252 KB Ok
21 Correct 198 ms 44252 KB Ok
22 Correct 207 ms 44252 KB Ok
23 Correct 222 ms 44380 KB Ok
24 Correct 293 ms 35316 KB Ok
25 Correct 301 ms 35292 KB Ok
26 Correct 275 ms 35676 KB Ok
27 Correct 313 ms 35676 KB Ok
28 Correct 283 ms 35164 KB Ok
29 Correct 301 ms 38236 KB Ok
30 Correct 288 ms 35548 KB Ok
31 Correct 322 ms 35164 KB Ok
32 Correct 315 ms 35196 KB Ok
33 Correct 302 ms 35548 KB Ok
34 Correct 571 ms 44508 KB Ok
35 Correct 358 ms 44704 KB Ok
36 Correct 516 ms 44508 KB Ok
37 Correct 366 ms 44508 KB Ok
38 Correct 374 ms 44508 KB Ok
39 Correct 516 ms 44444 KB Ok
40 Correct 413 ms 44508 KB Ok
41 Correct 345 ms 44508 KB Ok
42 Correct 528 ms 44508 KB Ok
43 Correct 383 ms 44508 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 44252 KB Ok
2 Correct 219 ms 44252 KB Ok
3 Correct 220 ms 35620 KB Ok
4 Correct 227 ms 36316 KB Ok
5 Correct 243 ms 35676 KB Ok
6 Correct 239 ms 37212 KB Ok
7 Correct 241 ms 35548 KB Ok
8 Correct 240 ms 37212 KB Ok
9 Correct 223 ms 35548 KB Ok
10 Correct 223 ms 39644 KB Ok
11 Correct 255 ms 35420 KB Ok
12 Correct 206 ms 35256 KB Ok
13 Correct 190 ms 44252 KB Ok
14 Correct 242 ms 44252 KB Ok
15 Correct 224 ms 44408 KB Ok
16 Correct 228 ms 44380 KB Ok
17 Correct 258 ms 44412 KB Ok
18 Correct 197 ms 44380 KB Ok
19 Correct 210 ms 44636 KB Ok
20 Correct 201 ms 44636 KB Ok
21 Correct 220 ms 44756 KB Ok
22 Correct 211 ms 44636 KB Ok
23 Correct 85 ms 44252 KB Ok
24 Correct 194 ms 44252 KB Ok
25 Correct 188 ms 44252 KB Ok
26 Correct 196 ms 44252 KB Ok
27 Correct 202 ms 44380 KB Ok
28 Correct 197 ms 44276 KB Ok
29 Correct 196 ms 44380 KB Ok
30 Correct 204 ms 44252 KB Ok
31 Correct 198 ms 44252 KB Ok
32 Correct 207 ms 44252 KB Ok
33 Correct 222 ms 44380 KB Ok
34 Correct 293 ms 35316 KB Ok
35 Correct 301 ms 35292 KB Ok
36 Correct 275 ms 35676 KB Ok
37 Correct 313 ms 35676 KB Ok
38 Correct 283 ms 35164 KB Ok
39 Correct 301 ms 38236 KB Ok
40 Correct 288 ms 35548 KB Ok
41 Correct 322 ms 35164 KB Ok
42 Correct 315 ms 35196 KB Ok
43 Correct 302 ms 35548 KB Ok
44 Correct 571 ms 44508 KB Ok
45 Correct 358 ms 44704 KB Ok
46 Correct 516 ms 44508 KB Ok
47 Correct 366 ms 44508 KB Ok
48 Correct 374 ms 44508 KB Ok
49 Correct 516 ms 44444 KB Ok
50 Correct 413 ms 44508 KB Ok
51 Correct 345 ms 44508 KB Ok
52 Correct 528 ms 44508 KB Ok
53 Correct 383 ms 44508 KB Ok
54 Correct 549 ms 36572 KB Ok
55 Correct 631 ms 37124 KB Ok
56 Correct 611 ms 37084 KB Ok
57 Correct 442 ms 36316 KB Ok
58 Correct 521 ms 36716 KB Ok
59 Correct 460 ms 36444 KB Ok
60 Correct 411 ms 36188 KB Ok
61 Correct 449 ms 36340 KB Ok
62 Correct 573 ms 36700 KB Ok
63 Correct 488 ms 36444 KB Ok
64 Correct 663 ms 37148 KB Ok
65 Correct 529 ms 36700 KB Ok
66 Correct 501 ms 36444 KB Ok
67 Correct 433 ms 36572 KB Ok
68 Correct 531 ms 36532 KB Ok
69 Execution timed out 2045 ms 49348 KB Time limit exceeded
70 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 44252 KB Ok
2 Correct 219 ms 44252 KB Ok
3 Correct 220 ms 35620 KB Ok
4 Correct 227 ms 36316 KB Ok
5 Correct 243 ms 35676 KB Ok
6 Correct 239 ms 37212 KB Ok
7 Correct 241 ms 35548 KB Ok
8 Correct 240 ms 37212 KB Ok
9 Correct 223 ms 35548 KB Ok
10 Correct 223 ms 39644 KB Ok
11 Correct 255 ms 35420 KB Ok
12 Correct 206 ms 35256 KB Ok
13 Correct 190 ms 44252 KB Ok
14 Correct 242 ms 44252 KB Ok
15 Correct 224 ms 44408 KB Ok
16 Correct 228 ms 44380 KB Ok
17 Correct 258 ms 44412 KB Ok
18 Correct 197 ms 44380 KB Ok
19 Correct 210 ms 44636 KB Ok
20 Correct 201 ms 44636 KB Ok
21 Correct 220 ms 44756 KB Ok
22 Correct 211 ms 44636 KB Ok
23 Correct 85 ms 44252 KB Ok
24 Correct 194 ms 44252 KB Ok
25 Correct 188 ms 44252 KB Ok
26 Correct 196 ms 44252 KB Ok
27 Correct 202 ms 44380 KB Ok
28 Correct 197 ms 44276 KB Ok
29 Correct 196 ms 44380 KB Ok
30 Correct 204 ms 44252 KB Ok
31 Correct 198 ms 44252 KB Ok
32 Correct 207 ms 44252 KB Ok
33 Correct 222 ms 44380 KB Ok
34 Correct 197 ms 44252 KB Ok
35 Correct 213 ms 44252 KB Ok
36 Correct 227 ms 44380 KB Ok
37 Correct 244 ms 44252 KB Ok
38 Correct 240 ms 44252 KB Ok
39 Correct 804 ms 47828 KB Ok
40 Correct 628 ms 46428 KB Ok
41 Correct 1233 ms 49760 KB Ok
42 Correct 784 ms 48732 KB Ok
43 Correct 511 ms 45660 KB Ok
44 Correct 698 ms 47964 KB Ok
45 Correct 293 ms 35316 KB Ok
46 Correct 301 ms 35292 KB Ok
47 Correct 275 ms 35676 KB Ok
48 Correct 313 ms 35676 KB Ok
49 Correct 283 ms 35164 KB Ok
50 Correct 301 ms 38236 KB Ok
51 Correct 288 ms 35548 KB Ok
52 Correct 322 ms 35164 KB Ok
53 Correct 315 ms 35196 KB Ok
54 Correct 302 ms 35548 KB Ok
55 Correct 571 ms 44508 KB Ok
56 Correct 358 ms 44704 KB Ok
57 Correct 516 ms 44508 KB Ok
58 Correct 366 ms 44508 KB Ok
59 Correct 374 ms 44508 KB Ok
60 Correct 516 ms 44444 KB Ok
61 Correct 413 ms 44508 KB Ok
62 Correct 345 ms 44508 KB Ok
63 Correct 528 ms 44508 KB Ok
64 Correct 383 ms 44508 KB Ok
65 Correct 549 ms 36572 KB Ok
66 Correct 631 ms 37124 KB Ok
67 Correct 611 ms 37084 KB Ok
68 Correct 442 ms 36316 KB Ok
69 Correct 521 ms 36716 KB Ok
70 Correct 460 ms 36444 KB Ok
71 Correct 411 ms 36188 KB Ok
72 Correct 449 ms 36340 KB Ok
73 Correct 573 ms 36700 KB Ok
74 Correct 488 ms 36444 KB Ok
75 Correct 663 ms 37148 KB Ok
76 Correct 529 ms 36700 KB Ok
77 Correct 501 ms 36444 KB Ok
78 Correct 433 ms 36572 KB Ok
79 Correct 531 ms 36532 KB Ok
80 Execution timed out 2045 ms 49348 KB Time limit exceeded
81 Halted 0 ms 0 KB -