oj.uz

Submission #308486

# Submission time Handle Problem Language Result Execution time Memory
308486 2020-10-01T12:01:41 Z aZvezda Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 35820 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
template<class T> inline void fix(T &x) {if(labs(x) >= mod) {x %= mod;} if(x < 0) {x += mod;}}
#define out(x) cout << __LINE__ << ": " << (#x) << " = " << (x) << endl

const int MAX_N = 4e5 + 10;
vector<int> g[MAX_N];
int used[MAX_N];
int n, m;
int arr[MAX_N], pref[MAX_N];

vector<int> top;

bool eval(int x) {
    top.resize(0);
    for(int i = 0; i <= x; i ++) {
        g[i].resize(0);
        used[i] = 0;
    }
    for(int i = 0; i <= x; i ++) {
        if(i + n <= x) {
            g[i + n].push_back(i);
            used[i] ++;
        }
        if(i - m >= 0) {
            g[i - m].push_back(i);
            used[i] ++;
        }
    }
    for(int i = 0; i <= x; i ++) {
        if(used[i] == 0) {
            top.push_back(i);
        }
    }
    int ind = 0;
    while(ind < top.size()) {
        auto curr = top[ind]; ind ++;
        for(auto it : g[curr]) {
            used[it] --;
            if(used[it] == 0) {
                top.push_back(it);
            }
        }
    }
    return top.size() == x + 1;
}

void build(int x) {
    for(int i = 0; i <= x; i ++) {
        pref[top[i]] = i;
    }
    for(int i = 0; i < x; i ++) {
        arr[i] = pref[i + 1] - pref[i];
    }
}

void solve() {
    cin >> n >> m;
    int l = max(n - 1, m - 1), r = MAX_N - 2;
    while(l < r - 1) {
        int m = (l + r) / 2ll;
        //cout << l << " " << m << " " << r << endl;
        if(eval(m)) {
            l = m;
        } else {
            r = m;
        }
    }
    cout << l << endl;
    eval(l);
    build(l);
    for(int i = 0; i < l; i ++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t;
    cin >> t;
    while(t --) {
        solve();
    }
    return 0;
}

Compilation message

sequence.cpp: In function 'bool eval(int)':
sequence.cpp:45:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     while(ind < top.size()) {
      |           ~~~~^~~~~~~~~~~~
sequence.cpp:54:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |     return top.size() == x + 1;
      |            ~~~~~~~~~~~^~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 16760 KB Ok
2 Correct 110 ms 16836 KB Ok
3 Correct 110 ms 16760 KB Ok
4 Correct 109 ms 16760 KB Ok
5 Correct 99 ms 16888 KB Ok
6 Correct 111 ms 16768 KB Ok
7 Correct 109 ms 16840 KB Ok
8 Correct 99 ms 16836 KB Ok
9 Correct 110 ms 16760 KB Ok
10 Correct 105 ms 16896 KB Ok
11 Correct 100 ms 16768 KB Ok
12 Correct 112 ms 16768 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 16744 KB Ok
2 Correct 98 ms 16768 KB Ok
3 Correct 110 ms 16760 KB Ok
4 Correct 98 ms 16760 KB Ok
5 Correct 111 ms 16796 KB Ok
6 Correct 118 ms 17016 KB Ok
7 Correct 135 ms 17528 KB Ok
8 Correct 124 ms 17016 KB Ok
9 Correct 143 ms 17528 KB Ok
10 Correct 132 ms 17276 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 16760 KB Ok
2 Correct 111 ms 16760 KB Ok
3 Correct 107 ms 16760 KB Ok
4 Correct 110 ms 16768 KB Ok
5 Correct 109 ms 16760 KB Ok
6 Correct 109 ms 16832 KB Ok
7 Correct 98 ms 16768 KB Ok
8 Correct 108 ms 16760 KB Ok
9 Correct 95 ms 16760 KB Ok
10 Correct 106 ms 16768 KB Ok
11 Correct 109 ms 16760 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 16760 KB Ok
2 Correct 107 ms 16768 KB Ok
3 Correct 109 ms 16768 KB Ok
4 Correct 108 ms 16768 KB Ok
5 Correct 110 ms 16832 KB Ok
6 Correct 423 ms 23148 KB Ok
7 Correct 369 ms 22892 KB Ok
8 Correct 658 ms 25032 KB Ok
9 Correct 489 ms 25068 KB Ok
10 Correct 323 ms 20788 KB Ok
11 Correct 476 ms 24516 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 16760 KB Ok
2 Correct 110 ms 16836 KB Ok
3 Correct 110 ms 16760 KB Ok
4 Correct 109 ms 16760 KB Ok
5 Correct 99 ms 16888 KB Ok
6 Correct 111 ms 16768 KB Ok
7 Correct 109 ms 16840 KB Ok
8 Correct 99 ms 16836 KB Ok
9 Correct 110 ms 16760 KB Ok
10 Correct 105 ms 16896 KB Ok
11 Correct 100 ms 16768 KB Ok
12 Correct 112 ms 16768 KB Ok
13 Correct 51 ms 16760 KB Ok
14 Correct 111 ms 16760 KB Ok
15 Correct 107 ms 16760 KB Ok
16 Correct 110 ms 16768 KB Ok
17 Correct 109 ms 16760 KB Ok
18 Correct 109 ms 16832 KB Ok
19 Correct 98 ms 16768 KB Ok
20 Correct 108 ms 16760 KB Ok
21 Correct 95 ms 16760 KB Ok
22 Correct 106 ms 16768 KB Ok
23 Correct 109 ms 16760 KB Ok
24 Correct 116 ms 16888 KB Ok
25 Correct 116 ms 17016 KB Ok
26 Correct 124 ms 16864 KB Ok
27 Correct 115 ms 16896 KB Ok
28 Correct 115 ms 16952 KB Ok
29 Correct 117 ms 16888 KB Ok
30 Correct 105 ms 17016 KB Ok
31 Correct 106 ms 16892 KB Ok
32 Correct 115 ms 16888 KB Ok
33 Correct 114 ms 16892 KB Ok
34 Correct 122 ms 17016 KB Ok
35 Correct 111 ms 17016 KB Ok
36 Correct 120 ms 17016 KB Ok
37 Correct 121 ms 17020 KB Ok
38 Correct 123 ms 17016 KB Ok
39 Correct 122 ms 17016 KB Ok
40 Correct 124 ms 17144 KB Ok
41 Correct 124 ms 17016 KB Ok
42 Correct 126 ms 17024 KB Ok
43 Correct 123 ms 17016 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 16760 KB Ok
2 Correct 110 ms 16836 KB Ok
3 Correct 110 ms 16760 KB Ok
4 Correct 109 ms 16760 KB Ok
5 Correct 99 ms 16888 KB Ok
6 Correct 111 ms 16768 KB Ok
7 Correct 109 ms 16840 KB Ok
8 Correct 99 ms 16836 KB Ok
9 Correct 110 ms 16760 KB Ok
10 Correct 105 ms 16896 KB Ok
11 Correct 100 ms 16768 KB Ok
12 Correct 112 ms 16768 KB Ok
13 Correct 106 ms 16744 KB Ok
14 Correct 98 ms 16768 KB Ok
15 Correct 110 ms 16760 KB Ok
16 Correct 98 ms 16760 KB Ok
17 Correct 111 ms 16796 KB Ok
18 Correct 118 ms 17016 KB Ok
19 Correct 135 ms 17528 KB Ok
20 Correct 124 ms 17016 KB Ok
21 Correct 143 ms 17528 KB Ok
22 Correct 132 ms 17276 KB Ok
23 Correct 51 ms 16760 KB Ok
24 Correct 111 ms 16760 KB Ok
25 Correct 107 ms 16760 KB Ok
26 Correct 110 ms 16768 KB Ok
27 Correct 109 ms 16760 KB Ok
28 Correct 109 ms 16832 KB Ok
29 Correct 98 ms 16768 KB Ok
30 Correct 108 ms 16760 KB Ok
31 Correct 95 ms 16760 KB Ok
32 Correct 106 ms 16768 KB Ok
33 Correct 109 ms 16760 KB Ok
34 Correct 116 ms 16888 KB Ok
35 Correct 116 ms 17016 KB Ok
36 Correct 124 ms 16864 KB Ok
37 Correct 115 ms 16896 KB Ok
38 Correct 115 ms 16952 KB Ok
39 Correct 117 ms 16888 KB Ok
40 Correct 105 ms 17016 KB Ok
41 Correct 106 ms 16892 KB Ok
42 Correct 115 ms 16888 KB Ok
43 Correct 114 ms 16892 KB Ok
44 Correct 122 ms 17016 KB Ok
45 Correct 111 ms 17016 KB Ok
46 Correct 120 ms 17016 KB Ok
47 Correct 121 ms 17020 KB Ok
48 Correct 123 ms 17016 KB Ok
49 Correct 122 ms 17016 KB Ok
50 Correct 124 ms 17144 KB Ok
51 Correct 124 ms 17016 KB Ok
52 Correct 126 ms 17024 KB Ok
53 Correct 123 ms 17016 KB Ok
54 Correct 359 ms 20200 KB Ok
55 Correct 407 ms 20460 KB Ok
56 Correct 399 ms 20468 KB Ok
57 Correct 308 ms 19824 KB Ok
58 Correct 367 ms 20208 KB Ok
59 Correct 351 ms 20096 KB Ok
60 Correct 306 ms 19824 KB Ok
61 Correct 317 ms 20084 KB Ok
62 Correct 428 ms 20472 KB Ok
63 Correct 325 ms 19948 KB Ok
64 Correct 405 ms 20432 KB Ok
65 Correct 380 ms 20336 KB Ok
66 Correct 341 ms 20080 KB Ok
67 Correct 291 ms 19952 KB Ok
68 Correct 352 ms 20148 KB Ok
69 Correct 904 ms 24432 KB Ok
70 Correct 969 ms 25528 KB Ok
71 Correct 867 ms 23544 KB Ok
72 Correct 890 ms 24684 KB Ok
73 Correct 919 ms 24076 KB Ok
74 Correct 803 ms 23152 KB Ok
75 Correct 815 ms 23152 KB Ok
76 Correct 973 ms 25328 KB Ok
77 Correct 807 ms 22892 KB Ok
78 Correct 947 ms 24984 KB Ok
79 Correct 894 ms 24604 KB Ok
80 Correct 833 ms 24176 KB Ok
81 Correct 934 ms 24944 KB Ok
82 Correct 845 ms 24304 KB Ok
83 Correct 797 ms 23404 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 16760 KB Ok
2 Correct 110 ms 16836 KB Ok
3 Correct 110 ms 16760 KB Ok
4 Correct 109 ms 16760 KB Ok
5 Correct 99 ms 16888 KB Ok
6 Correct 111 ms 16768 KB Ok
7 Correct 109 ms 16840 KB Ok
8 Correct 99 ms 16836 KB Ok
9 Correct 110 ms 16760 KB Ok
10 Correct 105 ms 16896 KB Ok
11 Correct 100 ms 16768 KB Ok
12 Correct 112 ms 16768 KB Ok
13 Correct 106 ms 16744 KB Ok
14 Correct 98 ms 16768 KB Ok
15 Correct 110 ms 16760 KB Ok
16 Correct 98 ms 16760 KB Ok
17 Correct 111 ms 16796 KB Ok
18 Correct 118 ms 17016 KB Ok
19 Correct 135 ms 17528 KB Ok
20 Correct 124 ms 17016 KB Ok
21 Correct 143 ms 17528 KB Ok
22 Correct 132 ms 17276 KB Ok
23 Correct 51 ms 16760 KB Ok
24 Correct 111 ms 16760 KB Ok
25 Correct 107 ms 16760 KB Ok
26 Correct 110 ms 16768 KB Ok
27 Correct 109 ms 16760 KB Ok
28 Correct 109 ms 16832 KB Ok
29 Correct 98 ms 16768 KB Ok
30 Correct 108 ms 16760 KB Ok
31 Correct 95 ms 16760 KB Ok
32 Correct 106 ms 16768 KB Ok
33 Correct 109 ms 16760 KB Ok
34 Correct 110 ms 16760 KB Ok
35 Correct 107 ms 16768 KB Ok
36 Correct 109 ms 16768 KB Ok
37 Correct 108 ms 16768 KB Ok
38 Correct 110 ms 16832 KB Ok
39 Correct 423 ms 23148 KB Ok
40 Correct 369 ms 22892 KB Ok
41 Correct 658 ms 25032 KB Ok
42 Correct 489 ms 25068 KB Ok
43 Correct 323 ms 20788 KB Ok
44 Correct 476 ms 24516 KB Ok
45 Correct 116 ms 16888 KB Ok
46 Correct 116 ms 17016 KB Ok
47 Correct 124 ms 16864 KB Ok
48 Correct 115 ms 16896 KB Ok
49 Correct 115 ms 16952 KB Ok
50 Correct 117 ms 16888 KB Ok
51 Correct 105 ms 17016 KB Ok
52 Correct 106 ms 16892 KB Ok
53 Correct 115 ms 16888 KB Ok
54 Correct 114 ms 16892 KB Ok
55 Correct 122 ms 17016 KB Ok
56 Correct 111 ms 17016 KB Ok
57 Correct 120 ms 17016 KB Ok
58 Correct 121 ms 17020 KB Ok
59 Correct 123 ms 17016 KB Ok
60 Correct 122 ms 17016 KB Ok
61 Correct 124 ms 17144 KB Ok
62 Correct 124 ms 17016 KB Ok
63 Correct 126 ms 17024 KB Ok
64 Correct 123 ms 17016 KB Ok
65 Correct 359 ms 20200 KB Ok
66 Correct 407 ms 20460 KB Ok
67 Correct 399 ms 20468 KB Ok
68 Correct 308 ms 19824 KB Ok
69 Correct 367 ms 20208 KB Ok
70 Correct 351 ms 20096 KB Ok
71 Correct 306 ms 19824 KB Ok
72 Correct 317 ms 20084 KB Ok
73 Correct 428 ms 20472 KB Ok
74 Correct 325 ms 19948 KB Ok
75 Correct 405 ms 20432 KB Ok
76 Correct 380 ms 20336 KB Ok
77 Correct 341 ms 20080 KB Ok
78 Correct 291 ms 19952 KB Ok
79 Correct 352 ms 20148 KB Ok
80 Correct 904 ms 24432 KB Ok
81 Correct 969 ms 25528 KB Ok
82 Correct 867 ms 23544 KB Ok
83 Correct 890 ms 24684 KB Ok
84 Correct 919 ms 24076 KB Ok
85 Correct 803 ms 23152 KB Ok
86 Correct 815 ms 23152 KB Ok
87 Correct 973 ms 25328 KB Ok
88 Correct 807 ms 22892 KB Ok
89 Correct 947 ms 24984 KB Ok
90 Correct 894 ms 24604 KB Ok
91 Correct 833 ms 24176 KB Ok
92 Correct 934 ms 24944 KB Ok
93 Correct 845 ms 24304 KB Ok
94 Correct 797 ms 23404 KB Ok
95 Correct 760 ms 26476 KB Ok
96 Correct 1116 ms 31972 KB Ok
97 Correct 1136 ms 28392 KB Ok
98 Correct 770 ms 29412 KB Ok
99 Correct 1018 ms 27876 KB Ok
100 Correct 1034 ms 27880 KB Ok
101 Correct 1010 ms 30312 KB Ok
102 Correct 919 ms 28112 KB Ok
103 Correct 930 ms 30184 KB Ok
104 Correct 1133 ms 31212 KB Ok
105 Correct 1148 ms 31976 KB Ok
106 Correct 845 ms 31332 KB Ok
107 Correct 996 ms 30692 KB Ok
108 Correct 1175 ms 31336 KB Ok
109 Correct 978 ms 32448 KB Ok
110 Execution timed out 2100 ms 35820 KB Time limit exceeded
111 Halted 0 ms 0 KB -