oj.uz

Submission #77889

# Submission time Handle Problem Language Result Execution time Memory
77889 2018-10-01T04:13:28 Z antimirage Nice sequence (IZhO18_sequence) C++17
100 / 100
 1393 ms 38824 KB 
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <utility>
#include <memory.h>
#include <set>
#include <queue>
#include <map>

#define fr first
#define sc second
#define mk make_pair
#define pb emplace_back
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 1e6 + 5;

int n, m, tests, deg[N], u[N], ans[N];

vector <int> vec, topo;

inline bool check (int len, bool fl = false)
{
    if (fl)
        topo.clear();

    memset(deg, 0, sizeof(deg));

    for (int i = 0; i <= len; i++)
    {
        if (i + n <= len)
            deg[i + n]++;
        if (i + m <= len)
            deg[i]++;
    }
    for (int i = 0; i <= len; i++)
    {
        if(!deg[i])
            vec.pb(i);
    }
    while (!vec.empty() )
    {
        int v = vec.back();
        vec.pop_back();

        if (v + n <= len && deg[v + n])
        {
            vec.pb(v + n);
            deg[v + n]--;
        }
        if (v - m >= 0 && deg[v - m])
        {
            vec.pb(v - m);
            deg[v - m]--;
        }
        if(fl)
            topo.pb(v);
    }
    for (int i = 0; i <= len; i++)
    {
        if (deg[i])
            return false;
    }
    return true;
}
main()
{
    cin >> tests;
    while (tests--)
    {
        scanf("%d%d", &n, &m);

        swap(n, m);
        int l = 0, r = 1e6;

        while (r - l > 1)
        {
            int md = (l + r) >> 1;
            if ( check(md) )
                l = md;
            else
                r = md;
        }
        check(l, 1);
        printf("%d\n", l);

        int pos = lower_bound ( all(topo), 0 ) - topo.begin();
        for (int i = 0; i <= l; i++)
            ans[topo[i]] = i - pos;

        for (int i = 1; i <= l; i++)
            printf("%d ", ans[i] - ans[i - 1]);

        printf("\n");
    }
}

Compilation message

sequence.cpp:71:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
sequence.cpp: In function 'int main()':
sequence.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &n, &m);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 4216 KB Ok
2 Correct 89 ms 4352 KB Ok
3 Correct 94 ms 4560 KB Ok
4 Correct 99 ms 4640 KB Ok
5 Correct 91 ms 4640 KB Ok
6 Correct 91 ms 4640 KB Ok
7 Correct 92 ms 4640 KB Ok
8 Correct 92 ms 4640 KB Ok
9 Correct 92 ms 4640 KB Ok
10 Correct 94 ms 4740 KB Ok
11 Correct 103 ms 4740 KB Ok
12 Correct 96 ms 4852 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 4852 KB Ok
2 Correct 93 ms 4852 KB Ok
3 Correct 94 ms 4852 KB Ok
4 Correct 105 ms 4852 KB Ok
5 Correct 104 ms 4852 KB Ok
6 Correct 108 ms 4900 KB Ok
7 Correct 111 ms 5416 KB Ok
8 Correct 104 ms 5416 KB Ok
9 Correct 134 ms 5556 KB Ok
10 Correct 101 ms 5556 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5556 KB Ok
2 Correct 94 ms 5556 KB Ok
3 Correct 93 ms 5556 KB Ok
4 Correct 94 ms 5556 KB Ok
5 Correct 95 ms 5556 KB Ok
6 Correct 93 ms 5556 KB Ok
7 Correct 92 ms 5556 KB Ok
8 Correct 93 ms 5556 KB Ok
9 Correct 95 ms 5556 KB Ok
10 Correct 92 ms 5556 KB Ok
11 Correct 92 ms 5556 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 5556 KB Ok
2 Correct 93 ms 5556 KB Ok
3 Correct 91 ms 5556 KB Ok
4 Correct 101 ms 5556 KB Ok
5 Correct 92 ms 5556 KB Ok
6 Correct 299 ms 10780 KB Ok
7 Correct 248 ms 10780 KB Ok
8 Correct 434 ms 12824 KB Ok
9 Correct 374 ms 12824 KB Ok
10 Correct 238 ms 12824 KB Ok
11 Correct 339 ms 12824 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 4216 KB Ok
2 Correct 89 ms 4352 KB Ok
3 Correct 94 ms 4560 KB Ok
4 Correct 99 ms 4640 KB Ok
5 Correct 91 ms 4640 KB Ok
6 Correct 91 ms 4640 KB Ok
7 Correct 92 ms 4640 KB Ok
8 Correct 92 ms 4640 KB Ok
9 Correct 92 ms 4640 KB Ok
10 Correct 94 ms 4740 KB Ok
11 Correct 103 ms 4740 KB Ok
12 Correct 96 ms 4852 KB Ok
13 Correct 31 ms 5556 KB Ok
14 Correct 94 ms 5556 KB Ok
15 Correct 93 ms 5556 KB Ok
16 Correct 94 ms 5556 KB Ok
17 Correct 95 ms 5556 KB Ok
18 Correct 93 ms 5556 KB Ok
19 Correct 92 ms 5556 KB Ok
20 Correct 93 ms 5556 KB Ok
21 Correct 95 ms 5556 KB Ok
22 Correct 92 ms 5556 KB Ok
23 Correct 92 ms 5556 KB Ok
24 Correct 96 ms 12824 KB Ok
25 Correct 95 ms 12824 KB Ok
26 Correct 98 ms 12824 KB Ok
27 Correct 97 ms 12824 KB Ok
28 Correct 103 ms 12824 KB Ok
29 Correct 93 ms 12824 KB Ok
30 Correct 97 ms 12824 KB Ok
31 Correct 94 ms 12824 KB Ok
32 Correct 97 ms 12824 KB Ok
33 Correct 99 ms 12824 KB Ok
34 Correct 99 ms 12824 KB Ok
35 Correct 105 ms 12824 KB Ok
36 Correct 105 ms 12824 KB Ok
37 Correct 97 ms 12824 KB Ok
38 Correct 109 ms 12824 KB Ok
39 Correct 99 ms 12824 KB Ok
40 Correct 98 ms 12824 KB Ok
41 Correct 102 ms 12824 KB Ok
42 Correct 100 ms 12824 KB Ok
43 Correct 97 ms 12824 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 4216 KB Ok
2 Correct 89 ms 4352 KB Ok
3 Correct 94 ms 4560 KB Ok
4 Correct 99 ms 4640 KB Ok
5 Correct 91 ms 4640 KB Ok
6 Correct 91 ms 4640 KB Ok
7 Correct 92 ms 4640 KB Ok
8 Correct 92 ms 4640 KB Ok
9 Correct 92 ms 4640 KB Ok
10 Correct 94 ms 4740 KB Ok
11 Correct 103 ms 4740 KB Ok
12 Correct 96 ms 4852 KB Ok
13 Correct 93 ms 4852 KB Ok
14 Correct 93 ms 4852 KB Ok
15 Correct 94 ms 4852 KB Ok
16 Correct 105 ms 4852 KB Ok
17 Correct 104 ms 4852 KB Ok
18 Correct 108 ms 4900 KB Ok
19 Correct 111 ms 5416 KB Ok
20 Correct 104 ms 5416 KB Ok
21 Correct 134 ms 5556 KB Ok
22 Correct 101 ms 5556 KB Ok
23 Correct 31 ms 5556 KB Ok
24 Correct 94 ms 5556 KB Ok
25 Correct 93 ms 5556 KB Ok
26 Correct 94 ms 5556 KB Ok
27 Correct 95 ms 5556 KB Ok
28 Correct 93 ms 5556 KB Ok
29 Correct 92 ms 5556 KB Ok
30 Correct 93 ms 5556 KB Ok
31 Correct 95 ms 5556 KB Ok
32 Correct 92 ms 5556 KB Ok
33 Correct 92 ms 5556 KB Ok
34 Correct 96 ms 12824 KB Ok
35 Correct 95 ms 12824 KB Ok
36 Correct 98 ms 12824 KB Ok
37 Correct 97 ms 12824 KB Ok
38 Correct 103 ms 12824 KB Ok
39 Correct 93 ms 12824 KB Ok
40 Correct 97 ms 12824 KB Ok
41 Correct 94 ms 12824 KB Ok
42 Correct 97 ms 12824 KB Ok
43 Correct 99 ms 12824 KB Ok
44 Correct 99 ms 12824 KB Ok
45 Correct 105 ms 12824 KB Ok
46 Correct 105 ms 12824 KB Ok
47 Correct 97 ms 12824 KB Ok
48 Correct 109 ms 12824 KB Ok
49 Correct 99 ms 12824 KB Ok
50 Correct 98 ms 12824 KB Ok
51 Correct 102 ms 12824 KB Ok
52 Correct 100 ms 12824 KB Ok
53 Correct 97 ms 12824 KB Ok
54 Correct 278 ms 12824 KB Ok
55 Correct 304 ms 12824 KB Ok
56 Correct 312 ms 12824 KB Ok
57 Correct 248 ms 12824 KB Ok
58 Correct 279 ms 12824 KB Ok
59 Correct 277 ms 12824 KB Ok
60 Correct 249 ms 12824 KB Ok
61 Correct 259 ms 12824 KB Ok
62 Correct 330 ms 12824 KB Ok
63 Correct 275 ms 12824 KB Ok
64 Correct 305 ms 12824 KB Ok
65 Correct 292 ms 12824 KB Ok
66 Correct 286 ms 12824 KB Ok
67 Correct 256 ms 12824 KB Ok
68 Correct 284 ms 12824 KB Ok
69 Correct 374 ms 12824 KB Ok
70 Correct 356 ms 13136 KB Ok
71 Correct 397 ms 13144 KB Ok
72 Correct 350 ms 13144 KB Ok
73 Correct 386 ms 13144 KB Ok
74 Correct 374 ms 13268 KB Ok
75 Correct 361 ms 13268 KB Ok
76 Correct 375 ms 13268 KB Ok
77 Correct 373 ms 13268 KB Ok
78 Correct 398 ms 13268 KB Ok
79 Correct 360 ms 13268 KB Ok
80 Correct 389 ms 13268 KB Ok
81 Correct 379 ms 13268 KB Ok
82 Correct 382 ms 13268 KB Ok
83 Correct 384 ms 13268 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 4216 KB Ok
2 Correct 89 ms 4352 KB Ok
3 Correct 94 ms 4560 KB Ok
4 Correct 99 ms 4640 KB Ok
5 Correct 91 ms 4640 KB Ok
6 Correct 91 ms 4640 KB Ok
7 Correct 92 ms 4640 KB Ok
8 Correct 92 ms 4640 KB Ok
9 Correct 92 ms 4640 KB Ok
10 Correct 94 ms 4740 KB Ok
11 Correct 103 ms 4740 KB Ok
12 Correct 96 ms 4852 KB Ok
13 Correct 93 ms 4852 KB Ok
14 Correct 93 ms 4852 KB Ok
15 Correct 94 ms 4852 KB Ok
16 Correct 105 ms 4852 KB Ok
17 Correct 104 ms 4852 KB Ok
18 Correct 108 ms 4900 KB Ok
19 Correct 111 ms 5416 KB Ok
20 Correct 104 ms 5416 KB Ok
21 Correct 134 ms 5556 KB Ok
22 Correct 101 ms 5556 KB Ok
23 Correct 31 ms 5556 KB Ok
24 Correct 94 ms 5556 KB Ok
25 Correct 93 ms 5556 KB Ok
26 Correct 94 ms 5556 KB Ok
27 Correct 95 ms 5556 KB Ok
28 Correct 93 ms 5556 KB Ok
29 Correct 92 ms 5556 KB Ok
30 Correct 93 ms 5556 KB Ok
31 Correct 95 ms 5556 KB Ok
32 Correct 92 ms 5556 KB Ok
33 Correct 92 ms 5556 KB Ok
34 Correct 96 ms 5556 KB Ok
35 Correct 93 ms 5556 KB Ok
36 Correct 91 ms 5556 KB Ok
37 Correct 101 ms 5556 KB Ok
38 Correct 92 ms 5556 KB Ok
39 Correct 299 ms 10780 KB Ok
40 Correct 248 ms 10780 KB Ok
41 Correct 434 ms 12824 KB Ok
42 Correct 374 ms 12824 KB Ok
43 Correct 238 ms 12824 KB Ok
44 Correct 339 ms 12824 KB Ok
45 Correct 96 ms 12824 KB Ok
46 Correct 95 ms 12824 KB Ok
47 Correct 98 ms 12824 KB Ok
48 Correct 97 ms 12824 KB Ok
49 Correct 103 ms 12824 KB Ok
50 Correct 93 ms 12824 KB Ok
51 Correct 97 ms 12824 KB Ok
52 Correct 94 ms 12824 KB Ok
53 Correct 97 ms 12824 KB Ok
54 Correct 99 ms 12824 KB Ok
55 Correct 99 ms 12824 KB Ok
56 Correct 105 ms 12824 KB Ok
57 Correct 105 ms 12824 KB Ok
58 Correct 97 ms 12824 KB Ok
59 Correct 109 ms 12824 KB Ok
60 Correct 99 ms 12824 KB Ok
61 Correct 98 ms 12824 KB Ok
62 Correct 102 ms 12824 KB Ok
63 Correct 100 ms 12824 KB Ok
64 Correct 97 ms 12824 KB Ok
65 Correct 278 ms 12824 KB Ok
66 Correct 304 ms 12824 KB Ok
67 Correct 312 ms 12824 KB Ok
68 Correct 248 ms 12824 KB Ok
69 Correct 279 ms 12824 KB Ok
70 Correct 277 ms 12824 KB Ok
71 Correct 249 ms 12824 KB Ok
72 Correct 259 ms 12824 KB Ok
73 Correct 330 ms 12824 KB Ok
74 Correct 275 ms 12824 KB Ok
75 Correct 305 ms 12824 KB Ok
76 Correct 292 ms 12824 KB Ok
77 Correct 286 ms 12824 KB Ok
78 Correct 256 ms 12824 KB Ok
79 Correct 284 ms 12824 KB Ok
80 Correct 374 ms 12824 KB Ok
81 Correct 356 ms 13136 KB Ok
82 Correct 397 ms 13144 KB Ok
83 Correct 350 ms 13144 KB Ok
84 Correct 386 ms 13144 KB Ok
85 Correct 374 ms 13268 KB Ok
86 Correct 361 ms 13268 KB Ok
87 Correct 375 ms 13268 KB Ok
88 Correct 373 ms 13268 KB Ok
89 Correct 398 ms 13268 KB Ok
90 Correct 360 ms 13268 KB Ok
91 Correct 389 ms 13268 KB Ok
92 Correct 379 ms 13268 KB Ok
93 Correct 382 ms 13268 KB Ok
94 Correct 384 ms 13268 KB Ok
95 Correct 585 ms 14412 KB Ok
96 Correct 856 ms 18432 KB Ok
97 Correct 802 ms 18432 KB Ok
98 Correct 616 ms 18432 KB Ok
99 Correct 748 ms 18432 KB Ok
100 Correct 822 ms 18432 KB Ok
101 Correct 836 ms 18432 KB Ok
102 Correct 745 ms 18432 KB Ok
103 Correct 742 ms 18432 KB Ok
104 Correct 827 ms 18880 KB Ok
105 Correct 783 ms 18880 KB Ok
106 Correct 669 ms 18880 KB Ok
107 Correct 752 ms 18880 KB Ok
108 Correct 809 ms 18880 KB Ok
109 Correct 767 ms 18880 KB Ok
110 Correct 1377 ms 36684 KB Ok
111 Correct 1270 ms 36896 KB Ok
112 Correct 1359 ms 38824 KB Ok
113 Correct 1341 ms 38824 KB Ok
114 Correct 1300 ms 38824 KB Ok
115 Correct 1377 ms 38824 KB Ok
116 Correct 1292 ms 38824 KB Ok
117 Correct 1263 ms 38824 KB Ok
118 Correct 1393 ms 38824 KB Ok
119 Correct 1327 ms 38824 KB Ok
120 Correct 1321 ms 38824 KB Ok
121 Correct 1317 ms 38824 KB Ok
122 Correct 1258 ms 38824 KB Ok
123 Correct 1357 ms 38824 KB Ok
124 Correct 1341 ms 38824 KB Ok
125 Correct 1140 ms 38824 KB Ok