oj.uz

Submission #633593

# Submission time Handle Problem Language Result Execution time Memory
633593 2022-08-22T19:23:38 Z fabijan_cikac Nice sequence (IZhO18_sequence) C++17
100 / 100
 1793 ms 47588 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

using namespace std;

#define ll long long int
#define pb push_back

const int N = 400100;
const ll INF = 1e18;

int t, n, m; int a[N];
int v[N][2];
int u[N][2]; int tme;

void rec(int x){
    if (u[x][0] != -1 && a[x] == 0) rec(u[x][0]);
    if (u[x][1] != -1 && a[x] == 0) rec(u[x][1]);
    a[x] = --tme;
}

int bio[N]; ll sz = 0;

bool dfs(int x){
	if(bio[x]) return bio[x] == 1;
	bio[x] = 1;
	if(v[x][0] != -1 && dfs(v[x][0])) return 1;
	if(v[x][1] != -1 && dfs(v[x][1])) return 1;
	bio[x] = 2;
	return 0;
}

void clear_it(int k){
    for (int i = 0; i <= k; ++i){
        bio[i] = 0;
        v[i][0] = -1; u[i][0] = -1;
        v[i][1] = -1; u[i][1] = -1;
    }
}

bool good_seq(int k, int samo = 1){
    if (k == 41381){
        cout << "";
    }
    clear_it(k);
    for (int i = n; i <= k; ++i){
        v[i - n][0] = i; u[i][0] = (i - n);
    }
    for (int i = m; i <= k; ++i){
        v[i][1] = (i - m); u[i - m][1] = i;
    }
    for (int i = 0; i <= k; ++i) a[i] = 0;
    for (int i = 0; i <= k; ++i){
        if (!bio[i]){
            if (dfs(i)) return 0;
        }
    }
    for (int i = 0; i <= k; ++i){
        if (!bio[i]) return 0;
    }
    if(samo) return 1;
    for (int i = 0; i <= k; ++i){
        if (a[i] == 0) rec(i);
    }
    for (int i = 1; i <= k; ++i) a[i] -= a[0];
    a[0] = 0; return 1;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    scanf("%d", &t); memset(v, -1, sizeof(v));
    memset(u, -1, sizeof(u));
    while (t--){
        if (t < 0) break;
        scanf("%d%d", &n, &m);
        int l = 0; int r = n + m + 1;
        while (l < r){
            //printf("%d %d\n", l, r);
            int mid = (l + r + 1) / 2;
            if (good_seq(mid))
                l = mid;
            else r = mid - 1;
        }
        good_seq(l, 0);
        printf("%d\n", l);
        for (int i = 1; i <= l; ++i)
            printf("%d ", a[i] - a[i - 1]);
        printf("\n");
    }

    return 0;
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     scanf("%d", &t); memset(v, -1, sizeof(v));
      |     ~~~~~^~~~~~~~~~
sequence.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         scanf("%d%d", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Ok
2 Correct 3 ms 6612 KB Ok
3 Correct 3 ms 6612 KB Ok
4 Correct 3 ms 6484 KB Ok
5 Correct 3 ms 6484 KB Ok
6 Correct 3 ms 6484 KB Ok
7 Correct 3 ms 6484 KB Ok
8 Correct 3 ms 6612 KB Ok
9 Correct 3 ms 6612 KB Ok
10 Correct 2 ms 6484 KB Ok
11 Correct 4 ms 6484 KB Ok
12 Correct 3 ms 6612 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Ok
2 Correct 2 ms 6612 KB Ok
3 Correct 3 ms 6484 KB Ok
4 Correct 3 ms 6484 KB Ok
5 Correct 3 ms 6524 KB Ok
6 Correct 6 ms 6612 KB Ok
7 Correct 16 ms 7340 KB Ok
8 Correct 9 ms 6840 KB Ok
9 Correct 17 ms 7380 KB Ok
10 Correct 11 ms 6920 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Ok
2 Correct 3 ms 6484 KB Ok
3 Correct 3 ms 6484 KB Ok
4 Correct 3 ms 6484 KB Ok
5 Correct 3 ms 6484 KB Ok
6 Correct 3 ms 6484 KB Ok
7 Correct 3 ms 6576 KB Ok
8 Correct 3 ms 6484 KB Ok
9 Correct 3 ms 6484 KB Ok
10 Correct 3 ms 6484 KB Ok
11 Correct 3 ms 6484 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Ok
2 Correct 3 ms 6524 KB Ok
3 Correct 3 ms 6484 KB Ok
4 Correct 3 ms 6612 KB Ok
5 Correct 3 ms 6612 KB Ok
6 Correct 143 ms 14956 KB Ok
7 Correct 154 ms 14948 KB Ok
8 Correct 246 ms 17268 KB Ok
9 Correct 186 ms 17616 KB Ok
10 Correct 94 ms 12360 KB Ok
11 Correct 154 ms 17524 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Ok
2 Correct 3 ms 6612 KB Ok
3 Correct 3 ms 6612 KB Ok
4 Correct 3 ms 6484 KB Ok
5 Correct 3 ms 6484 KB Ok
6 Correct 3 ms 6484 KB Ok
7 Correct 3 ms 6484 KB Ok
8 Correct 3 ms 6612 KB Ok
9 Correct 3 ms 6612 KB Ok
10 Correct 2 ms 6484 KB Ok
11 Correct 4 ms 6484 KB Ok
12 Correct 3 ms 6612 KB Ok
13 Correct 3 ms 6484 KB Ok
14 Correct 3 ms 6484 KB Ok
15 Correct 3 ms 6484 KB Ok
16 Correct 3 ms 6484 KB Ok
17 Correct 3 ms 6484 KB Ok
18 Correct 3 ms 6484 KB Ok
19 Correct 3 ms 6576 KB Ok
20 Correct 3 ms 6484 KB Ok
21 Correct 3 ms 6484 KB Ok
22 Correct 3 ms 6484 KB Ok
23 Correct 3 ms 6484 KB Ok
24 Correct 6 ms 6612 KB Ok
25 Correct 5 ms 6596 KB Ok
26 Correct 6 ms 6612 KB Ok
27 Correct 5 ms 6612 KB Ok
28 Correct 4 ms 6612 KB Ok
29 Correct 4 ms 6612 KB Ok
30 Correct 5 ms 6612 KB Ok
31 Correct 5 ms 6612 KB Ok
32 Correct 4 ms 6612 KB Ok
33 Correct 4 ms 6660 KB Ok
34 Correct 8 ms 6868 KB Ok
35 Correct 12 ms 6868 KB Ok
36 Correct 8 ms 6852 KB Ok
37 Correct 8 ms 6868 KB Ok
38 Correct 10 ms 6868 KB Ok
39 Correct 8 ms 6740 KB Ok
40 Correct 9 ms 6868 KB Ok
41 Correct 9 ms 6868 KB Ok
42 Correct 8 ms 6760 KB Ok
43 Correct 8 ms 6836 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Ok
2 Correct 3 ms 6612 KB Ok
3 Correct 3 ms 6612 KB Ok
4 Correct 3 ms 6484 KB Ok
5 Correct 3 ms 6484 KB Ok
6 Correct 3 ms 6484 KB Ok
7 Correct 3 ms 6484 KB Ok
8 Correct 3 ms 6612 KB Ok
9 Correct 3 ms 6612 KB Ok
10 Correct 2 ms 6484 KB Ok
11 Correct 4 ms 6484 KB Ok
12 Correct 3 ms 6612 KB Ok
13 Correct 3 ms 6484 KB Ok
14 Correct 2 ms 6612 KB Ok
15 Correct 3 ms 6484 KB Ok
16 Correct 3 ms 6484 KB Ok
17 Correct 3 ms 6524 KB Ok
18 Correct 6 ms 6612 KB Ok
19 Correct 16 ms 7340 KB Ok
20 Correct 9 ms 6840 KB Ok
21 Correct 17 ms 7380 KB Ok
22 Correct 11 ms 6920 KB Ok
23 Correct 3 ms 6484 KB Ok
24 Correct 3 ms 6484 KB Ok
25 Correct 3 ms 6484 KB Ok
26 Correct 3 ms 6484 KB Ok
27 Correct 3 ms 6484 KB Ok
28 Correct 3 ms 6484 KB Ok
29 Correct 3 ms 6576 KB Ok
30 Correct 3 ms 6484 KB Ok
31 Correct 3 ms 6484 KB Ok
32 Correct 3 ms 6484 KB Ok
33 Correct 3 ms 6484 KB Ok
34 Correct 6 ms 6612 KB Ok
35 Correct 5 ms 6596 KB Ok
36 Correct 6 ms 6612 KB Ok
37 Correct 5 ms 6612 KB Ok
38 Correct 4 ms 6612 KB Ok
39 Correct 4 ms 6612 KB Ok
40 Correct 5 ms 6612 KB Ok
41 Correct 5 ms 6612 KB Ok
42 Correct 4 ms 6612 KB Ok
43 Correct 4 ms 6660 KB Ok
44 Correct 8 ms 6868 KB Ok
45 Correct 12 ms 6868 KB Ok
46 Correct 8 ms 6852 KB Ok
47 Correct 8 ms 6868 KB Ok
48 Correct 10 ms 6868 KB Ok
49 Correct 8 ms 6740 KB Ok
50 Correct 9 ms 6868 KB Ok
51 Correct 9 ms 6868 KB Ok
52 Correct 8 ms 6760 KB Ok
53 Correct 8 ms 6836 KB Ok
54 Correct 104 ms 9456 KB Ok
55 Correct 122 ms 9868 KB Ok
56 Correct 125 ms 9696 KB Ok
57 Correct 90 ms 8956 KB Ok
58 Correct 101 ms 9804 KB Ok
59 Correct 87 ms 9576 KB Ok
60 Correct 80 ms 9128 KB Ok
61 Correct 91 ms 9140 KB Ok
62 Correct 104 ms 10048 KB Ok
63 Correct 91 ms 9300 KB Ok
64 Correct 110 ms 9844 KB Ok
65 Correct 97 ms 9696 KB Ok
66 Correct 91 ms 9380 KB Ok
67 Correct 86 ms 9108 KB Ok
68 Correct 94 ms 9496 KB Ok
69 Correct 204 ms 15828 KB Ok
70 Correct 218 ms 16144 KB Ok
71 Correct 220 ms 15864 KB Ok
72 Correct 199 ms 15656 KB Ok
73 Correct 194 ms 16068 KB Ok
74 Correct 197 ms 15880 KB Ok
75 Correct 243 ms 15704 KB Ok
76 Correct 238 ms 15872 KB Ok
77 Correct 199 ms 15788 KB Ok
78 Correct 222 ms 15720 KB Ok
79 Correct 214 ms 16076 KB Ok
80 Correct 206 ms 15776 KB Ok
81 Correct 213 ms 16076 KB Ok
82 Correct 211 ms 15872 KB Ok
83 Correct 198 ms 15948 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Ok
2 Correct 3 ms 6612 KB Ok
3 Correct 3 ms 6612 KB Ok
4 Correct 3 ms 6484 KB Ok
5 Correct 3 ms 6484 KB Ok
6 Correct 3 ms 6484 KB Ok
7 Correct 3 ms 6484 KB Ok
8 Correct 3 ms 6612 KB Ok
9 Correct 3 ms 6612 KB Ok
10 Correct 2 ms 6484 KB Ok
11 Correct 4 ms 6484 KB Ok
12 Correct 3 ms 6612 KB Ok
13 Correct 3 ms 6484 KB Ok
14 Correct 2 ms 6612 KB Ok
15 Correct 3 ms 6484 KB Ok
16 Correct 3 ms 6484 KB Ok
17 Correct 3 ms 6524 KB Ok
18 Correct 6 ms 6612 KB Ok
19 Correct 16 ms 7340 KB Ok
20 Correct 9 ms 6840 KB Ok
21 Correct 17 ms 7380 KB Ok
22 Correct 11 ms 6920 KB Ok
23 Correct 3 ms 6484 KB Ok
24 Correct 3 ms 6484 KB Ok
25 Correct 3 ms 6484 KB Ok
26 Correct 3 ms 6484 KB Ok
27 Correct 3 ms 6484 KB Ok
28 Correct 3 ms 6484 KB Ok
29 Correct 3 ms 6576 KB Ok
30 Correct 3 ms 6484 KB Ok
31 Correct 3 ms 6484 KB Ok
32 Correct 3 ms 6484 KB Ok
33 Correct 3 ms 6484 KB Ok
34 Correct 3 ms 6484 KB Ok
35 Correct 3 ms 6524 KB Ok
36 Correct 3 ms 6484 KB Ok
37 Correct 3 ms 6612 KB Ok
38 Correct 3 ms 6612 KB Ok
39 Correct 143 ms 14956 KB Ok
40 Correct 154 ms 14948 KB Ok
41 Correct 246 ms 17268 KB Ok
42 Correct 186 ms 17616 KB Ok
43 Correct 94 ms 12360 KB Ok
44 Correct 154 ms 17524 KB Ok
45 Correct 6 ms 6612 KB Ok
46 Correct 5 ms 6596 KB Ok
47 Correct 6 ms 6612 KB Ok
48 Correct 5 ms 6612 KB Ok
49 Correct 4 ms 6612 KB Ok
50 Correct 4 ms 6612 KB Ok
51 Correct 5 ms 6612 KB Ok
52 Correct 5 ms 6612 KB Ok
53 Correct 4 ms 6612 KB Ok
54 Correct 4 ms 6660 KB Ok
55 Correct 8 ms 6868 KB Ok
56 Correct 12 ms 6868 KB Ok
57 Correct 8 ms 6852 KB Ok
58 Correct 8 ms 6868 KB Ok
59 Correct 10 ms 6868 KB Ok
60 Correct 8 ms 6740 KB Ok
61 Correct 9 ms 6868 KB Ok
62 Correct 9 ms 6868 KB Ok
63 Correct 8 ms 6760 KB Ok
64 Correct 8 ms 6836 KB Ok
65 Correct 104 ms 9456 KB Ok
66 Correct 122 ms 9868 KB Ok
67 Correct 125 ms 9696 KB Ok
68 Correct 90 ms 8956 KB Ok
69 Correct 101 ms 9804 KB Ok
70 Correct 87 ms 9576 KB Ok
71 Correct 80 ms 9128 KB Ok
72 Correct 91 ms 9140 KB Ok
73 Correct 104 ms 10048 KB Ok
74 Correct 91 ms 9300 KB Ok
75 Correct 110 ms 9844 KB Ok
76 Correct 97 ms 9696 KB Ok
77 Correct 91 ms 9380 KB Ok
78 Correct 86 ms 9108 KB Ok
79 Correct 94 ms 9496 KB Ok
80 Correct 204 ms 15828 KB Ok
81 Correct 218 ms 16144 KB Ok
82 Correct 220 ms 15864 KB Ok
83 Correct 199 ms 15656 KB Ok
84 Correct 194 ms 16068 KB Ok
85 Correct 197 ms 15880 KB Ok
86 Correct 243 ms 15704 KB Ok
87 Correct 238 ms 15872 KB Ok
88 Correct 199 ms 15788 KB Ok
89 Correct 222 ms 15720 KB Ok
90 Correct 214 ms 16076 KB Ok
91 Correct 206 ms 15776 KB Ok
92 Correct 213 ms 16076 KB Ok
93 Correct 211 ms 15872 KB Ok
94 Correct 198 ms 15948 KB Ok
95 Correct 251 ms 14068 KB Ok
96 Correct 363 ms 17760 KB Ok
97 Correct 339 ms 16652 KB Ok
98 Correct 241 ms 14908 KB Ok
99 Correct 301 ms 15524 KB Ok
100 Correct 341 ms 16336 KB Ok
101 Correct 334 ms 16108 KB Ok
102 Correct 328 ms 16168 KB Ok
103 Correct 329 ms 16588 KB Ok
104 Correct 407 ms 17444 KB Ok
105 Correct 366 ms 17700 KB Ok
106 Correct 304 ms 16064 KB Ok
107 Correct 332 ms 16832 KB Ok
108 Correct 369 ms 18012 KB Ok
109 Correct 348 ms 17100 KB Ok
110 Correct 1486 ms 45300 KB Ok
111 Correct 1793 ms 46880 KB Ok
112 Correct 1573 ms 47188 KB Ok
113 Correct 1678 ms 45700 KB Ok
114 Correct 1490 ms 47576 KB Ok
115 Correct 1608 ms 46976 KB Ok
116 Correct 1735 ms 47548 KB Ok
117 Correct 1768 ms 46080 KB Ok
118 Correct 1468 ms 47588 KB Ok
119 Correct 1731 ms 45736 KB Ok
120 Correct 1570 ms 46264 KB Ok
121 Correct 1605 ms 45900 KB Ok
122 Correct 1723 ms 46540 KB Ok
123 Correct 1746 ms 46832 KB Ok
124 Correct 1749 ms 47516 KB Ok
125 Correct 1131 ms 29116 KB Ok