oj.uz

Submission #879413

# Submission time Handle Problem Language Result Execution time Memory
879413 2023-11-27T10:29:40 Z vjudge1 Nice sequence (IZhO18_sequence) C++17
58 / 100
 2000 ms 100260 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10, MOD = 998244353;
 
int timer = 1,pref[N],n,m,used[N];
vector<int> g[N],ord;
bool ok = false;
void dfs(int v){
    used[v] = 1;
    for(int to:g[v]){
        if(used[to] == 1){
            ok = false;
        }
        if(!used[to]){
            dfs(to);
        }
    }
    used[v] = 2;
    ord.push_back(v);
}
bool can(int len){
    
    for(int i = 1;i <= len; i++){
        if(i - m >= 0){
            g[i - m].push_back(i);
        }
        if(i - n >= 0){
            g[i].push_back(i - n);
        }
    }
    for(int i = 0;i <= len;i++){
        if(!used[i]){
            dfs(i);
        }
    }
    reverse(ord.begin(),ord.end());
    for(auto i:ord){
        pref[i] = timer++;
    }
    bool res = ok;
    ok = true;
    timer = 1;
    ord.clear();
    for(int i = 0;i <= len;i++){
        g[i].clear();
    }
    for(int i = 0;i <= len;i++){
        used[i] = 0;
    }
    return res;
}
void test(){
    cin >> n >> m;
    int l = 0,r = 1e6;
    while(r - l > 1){
        int mid = (l + r) >> 1;
        if(can(mid)){
            l = mid;
        }else{
            r = mid;
        }
    }
    can(l);
    cout << l << '\n';
    for(int i = 1;i <= l;i++){
        cout << pref[i] - pref[i - 1] << ' ';
    }
    cout << '\n';
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        test();
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 94484 KB Ok
2 Correct 364 ms 94656 KB Ok
3 Correct 578 ms 72900 KB Ok
4 Correct 439 ms 74480 KB Ok
5 Correct 554 ms 72896 KB Ok
6 Correct 345 ms 77064 KB Ok
7 Correct 397 ms 72336 KB Ok
8 Correct 357 ms 76992 KB Ok
9 Correct 348 ms 72632 KB Ok
10 Correct 381 ms 82876 KB Ok
11 Correct 410 ms 72392 KB Ok
12 Correct 319 ms 69564 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 94656 KB Ok
2 Correct 337 ms 94660 KB Ok
3 Correct 415 ms 94564 KB Ok
4 Correct 409 ms 94652 KB Ok
5 Correct 391 ms 94480 KB Ok
6 Correct 360 ms 94656 KB Ok
7 Correct 366 ms 94932 KB Ok
8 Correct 331 ms 94936 KB Ok
9 Correct 336 ms 95136 KB Ok
10 Correct 374 ms 94912 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 94680 KB Ok
2 Correct 308 ms 94692 KB Ok
3 Correct 336 ms 94656 KB Ok
4 Correct 352 ms 94660 KB Ok
5 Correct 376 ms 94572 KB Ok
6 Correct 304 ms 94700 KB Ok
7 Correct 364 ms 94652 KB Ok
8 Correct 340 ms 94664 KB Ok
9 Correct 355 ms 94480 KB Ok
10 Correct 319 ms 94640 KB Ok
11 Correct 341 ms 94656 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 94624 KB Ok
2 Correct 343 ms 94572 KB Ok
3 Correct 413 ms 94700 KB Ok
4 Correct 396 ms 94556 KB Ok
5 Correct 437 ms 94656 KB Ok
6 Correct 713 ms 98244 KB Ok
7 Correct 526 ms 96448 KB Ok
8 Correct 992 ms 99244 KB Ok
9 Correct 620 ms 100144 KB Ok
10 Correct 446 ms 96932 KB Ok
11 Correct 714 ms 97576 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 94484 KB Ok
2 Correct 364 ms 94656 KB Ok
3 Correct 578 ms 72900 KB Ok
4 Correct 439 ms 74480 KB Ok
5 Correct 554 ms 72896 KB Ok
6 Correct 345 ms 77064 KB Ok
7 Correct 397 ms 72336 KB Ok
8 Correct 357 ms 76992 KB Ok
9 Correct 348 ms 72632 KB Ok
10 Correct 381 ms 82876 KB Ok
11 Correct 410 ms 72392 KB Ok
12 Correct 319 ms 69564 KB Ok
13 Correct 157 ms 94680 KB Ok
14 Correct 308 ms 94692 KB Ok
15 Correct 336 ms 94656 KB Ok
16 Correct 352 ms 94660 KB Ok
17 Correct 376 ms 94572 KB Ok
18 Correct 304 ms 94700 KB Ok
19 Correct 364 ms 94652 KB Ok
20 Correct 340 ms 94664 KB Ok
21 Correct 355 ms 94480 KB Ok
22 Correct 319 ms 94640 KB Ok
23 Correct 341 ms 94656 KB Ok
24 Correct 594 ms 69352 KB Ok
25 Correct 651 ms 69824 KB Ok
26 Correct 591 ms 70668 KB Ok
27 Correct 711 ms 70812 KB Ok
28 Correct 489 ms 71552 KB Ok
29 Correct 543 ms 79308 KB Ok
30 Correct 494 ms 71024 KB Ok
31 Correct 588 ms 70280 KB Ok
32 Correct 536 ms 70212 KB Ok
33 Correct 583 ms 71304 KB Ok
34 Correct 1247 ms 93552 KB Ok
35 Correct 687 ms 95244 KB Ok
36 Correct 1211 ms 94788 KB Ok
37 Correct 717 ms 94924 KB Ok
38 Correct 743 ms 94944 KB Ok
39 Correct 1111 ms 94696 KB Ok
40 Correct 901 ms 94836 KB Ok
41 Correct 722 ms 93880 KB Ok
42 Correct 1275 ms 94272 KB Ok
43 Correct 792 ms 94848 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 94484 KB Ok
2 Correct 364 ms 94656 KB Ok
3 Correct 578 ms 72900 KB Ok
4 Correct 439 ms 74480 KB Ok
5 Correct 554 ms 72896 KB Ok
6 Correct 345 ms 77064 KB Ok
7 Correct 397 ms 72336 KB Ok
8 Correct 357 ms 76992 KB Ok
9 Correct 348 ms 72632 KB Ok
10 Correct 381 ms 82876 KB Ok
11 Correct 410 ms 72392 KB Ok
12 Correct 319 ms 69564 KB Ok
13 Correct 324 ms 94656 KB Ok
14 Correct 337 ms 94660 KB Ok
15 Correct 415 ms 94564 KB Ok
16 Correct 409 ms 94652 KB Ok
17 Correct 391 ms 94480 KB Ok
18 Correct 360 ms 94656 KB Ok
19 Correct 366 ms 94932 KB Ok
20 Correct 331 ms 94936 KB Ok
21 Correct 336 ms 95136 KB Ok
22 Correct 374 ms 94912 KB Ok
23 Correct 157 ms 94680 KB Ok
24 Correct 308 ms 94692 KB Ok
25 Correct 336 ms 94656 KB Ok
26 Correct 352 ms 94660 KB Ok
27 Correct 376 ms 94572 KB Ok
28 Correct 304 ms 94700 KB Ok
29 Correct 364 ms 94652 KB Ok
30 Correct 340 ms 94664 KB Ok
31 Correct 355 ms 94480 KB Ok
32 Correct 319 ms 94640 KB Ok
33 Correct 341 ms 94656 KB Ok
34 Correct 594 ms 69352 KB Ok
35 Correct 651 ms 69824 KB Ok
36 Correct 591 ms 70668 KB Ok
37 Correct 711 ms 70812 KB Ok
38 Correct 489 ms 71552 KB Ok
39 Correct 543 ms 79308 KB Ok
40 Correct 494 ms 71024 KB Ok
41 Correct 588 ms 70280 KB Ok
42 Correct 536 ms 70212 KB Ok
43 Correct 583 ms 71304 KB Ok
44 Correct 1247 ms 93552 KB Ok
45 Correct 687 ms 95244 KB Ok
46 Correct 1211 ms 94788 KB Ok
47 Correct 717 ms 94924 KB Ok
48 Correct 743 ms 94944 KB Ok
49 Correct 1111 ms 94696 KB Ok
50 Correct 901 ms 94836 KB Ok
51 Correct 722 ms 93880 KB Ok
52 Correct 1275 ms 94272 KB Ok
53 Correct 792 ms 94848 KB Ok
54 Correct 471 ms 73368 KB Ok
55 Correct 516 ms 73760 KB Ok
56 Correct 467 ms 71380 KB Ok
57 Correct 403 ms 70848 KB Ok
58 Correct 525 ms 71360 KB Ok
59 Correct 448 ms 71360 KB Ok
60 Correct 438 ms 71108 KB Ok
61 Correct 422 ms 71884 KB Ok
62 Correct 544 ms 73784 KB Ok
63 Correct 450 ms 73336 KB Ok
64 Correct 549 ms 71504 KB Ok
65 Correct 500 ms 72392 KB Ok
66 Correct 425 ms 71868 KB Ok
67 Correct 424 ms 71684 KB Ok
68 Correct 540 ms 72296 KB Ok
69 Correct 1896 ms 98476 KB Ok
70 Correct 1849 ms 99812 KB Ok
71 Execution timed out 2023 ms 100260 KB Time limit exceeded
72 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 94484 KB Ok
2 Correct 364 ms 94656 KB Ok
3 Correct 578 ms 72900 KB Ok
4 Correct 439 ms 74480 KB Ok
5 Correct 554 ms 72896 KB Ok
6 Correct 345 ms 77064 KB Ok
7 Correct 397 ms 72336 KB Ok
8 Correct 357 ms 76992 KB Ok
9 Correct 348 ms 72632 KB Ok
10 Correct 381 ms 82876 KB Ok
11 Correct 410 ms 72392 KB Ok
12 Correct 319 ms 69564 KB Ok
13 Correct 324 ms 94656 KB Ok
14 Correct 337 ms 94660 KB Ok
15 Correct 415 ms 94564 KB Ok
16 Correct 409 ms 94652 KB Ok
17 Correct 391 ms 94480 KB Ok
18 Correct 360 ms 94656 KB Ok
19 Correct 366 ms 94932 KB Ok
20 Correct 331 ms 94936 KB Ok
21 Correct 336 ms 95136 KB Ok
22 Correct 374 ms 94912 KB Ok
23 Correct 157 ms 94680 KB Ok
24 Correct 308 ms 94692 KB Ok
25 Correct 336 ms 94656 KB Ok
26 Correct 352 ms 94660 KB Ok
27 Correct 376 ms 94572 KB Ok
28 Correct 304 ms 94700 KB Ok
29 Correct 364 ms 94652 KB Ok
30 Correct 340 ms 94664 KB Ok
31 Correct 355 ms 94480 KB Ok
32 Correct 319 ms 94640 KB Ok
33 Correct 341 ms 94656 KB Ok
34 Correct 332 ms 94624 KB Ok
35 Correct 343 ms 94572 KB Ok
36 Correct 413 ms 94700 KB Ok
37 Correct 396 ms 94556 KB Ok
38 Correct 437 ms 94656 KB Ok
39 Correct 713 ms 98244 KB Ok
40 Correct 526 ms 96448 KB Ok
41 Correct 992 ms 99244 KB Ok
42 Correct 620 ms 100144 KB Ok
43 Correct 446 ms 96932 KB Ok
44 Correct 714 ms 97576 KB Ok
45 Correct 594 ms 69352 KB Ok
46 Correct 651 ms 69824 KB Ok
47 Correct 591 ms 70668 KB Ok
48 Correct 711 ms 70812 KB Ok
49 Correct 489 ms 71552 KB Ok
50 Correct 543 ms 79308 KB Ok
51 Correct 494 ms 71024 KB Ok
52 Correct 588 ms 70280 KB Ok
53 Correct 536 ms 70212 KB Ok
54 Correct 583 ms 71304 KB Ok
55 Correct 1247 ms 93552 KB Ok
56 Correct 687 ms 95244 KB Ok
57 Correct 1211 ms 94788 KB Ok
58 Correct 717 ms 94924 KB Ok
59 Correct 743 ms 94944 KB Ok
60 Correct 1111 ms 94696 KB Ok
61 Correct 901 ms 94836 KB Ok
62 Correct 722 ms 93880 KB Ok
63 Correct 1275 ms 94272 KB Ok
64 Correct 792 ms 94848 KB Ok
65 Correct 471 ms 73368 KB Ok
66 Correct 516 ms 73760 KB Ok
67 Correct 467 ms 71380 KB Ok
68 Correct 403 ms 70848 KB Ok
69 Correct 525 ms 71360 KB Ok
70 Correct 448 ms 71360 KB Ok
71 Correct 438 ms 71108 KB Ok
72 Correct 422 ms 71884 KB Ok
73 Correct 544 ms 73784 KB Ok
74 Correct 450 ms 73336 KB Ok
75 Correct 549 ms 71504 KB Ok
76 Correct 500 ms 72392 KB Ok
77 Correct 425 ms 71868 KB Ok
78 Correct 424 ms 71684 KB Ok
79 Correct 540 ms 72296 KB Ok
80 Correct 1896 ms 98476 KB Ok
81 Correct 1849 ms 99812 KB Ok
82 Execution timed out 2023 ms 100260 KB Time limit exceeded
83 Halted 0 ms 0 KB -