oj.uz

Submission #519357

# Submission time Handle Problem Language Result Execution time Memory
519357 2022-01-26T08:58:02 Z Dasha_Gnedko Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 68400 KB 
#include <bits/stdc++.h>

//#include <ext/pb_ds/detail/standard_policies.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

using namespace std;

//using namespace __gnu_pbds;
//template <typename T> using ordered_set = tree <T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 gen(time(0));

#define ll long long
#define ld long double
#define pb push_back
#define F first
#define S second
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define sz(a) int32_t(a.size())
#define endl '\n'
//#define int long long

const int N = 1e6 + 100;
const int M = 31;
const int mod = 998244353;
const int inf = 1e9 + 7;

int a[N], n, m, u[N], can[N], fl;
vector < int > g[N], ve;

void DFS(int v, int c)
{
    if (!v) c = 0;
    a[v] = c;
    u[v] = 1;
    for(auto to: g[v])
    {
        if (u[to]) fl = 1;
        else DFS(to, c - 1);
    }
    if (c > 0) ve.pb(v);
}

bool good(int len)
{
    for(int i = 0; i <= len; i++)
    {
        can[i] = 1;
        g[i].clear();
    }
    for(int i = m; i <= len; i++)
    {
        g[i - m].pb(i);
        can[i] = 0;
        if (i - n >= 0)
        {
            g[i].pb(i - n);
            can[i - n] = 0;
        }
    }
    for(int i = 0; i <= len; i++)
        u[i] = 0;
    fl = 0;
    ve.clear();
    for(int i = 0; i <= len; i++)
    {
        if (!can[i]) continue;
        DFS(i, len);
    }
    if (fl) return 0;
    for(int i = 0; i < sz(ve); i++)
        a[ve[i]] = i + 1;
    for(int i = len; i >= 0; i--)
    {
        if (!u[i]) return 0;
        if (i) a[i] -= a[i - 1];
    }
    return 1;
}

void solve()
{
    cin >> n >> m;
    int x = n, y = m;
    if (n < m) swap(n, m);
    if (n % m == 0)
    {
        cout << n - 1 << endl;
        for(int i = 0; i < n - 1; i++)
        {
            if (x == max(x, y)) cout << "1 ";
            else cout << "-1 ";
        }
        cout << endl;
        return;
    }
    int l = n, r = 1e6, ans = -1;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (good(mid))
        {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    good(ans);
    cout << ans << endl;
    for(int i = 1; i <= ans; i++)
    {
        if (x > y) a[i] *= -1;
        cout << a[i] << " ";
    }
}

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

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif // LOCAL

    int T;
    cin >> T;
    while (T--)
        solve();
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23800 KB Ok
2 Correct 13 ms 23756 KB Ok
3 Correct 12 ms 23756 KB Ok
4 Correct 13 ms 23756 KB Ok
5 Correct 12 ms 23756 KB Ok
6 Correct 12 ms 23756 KB Ok
7 Correct 12 ms 23756 KB Ok
8 Correct 12 ms 23756 KB Ok
9 Correct 14 ms 23756 KB Ok
10 Correct 13 ms 23756 KB Ok
11 Correct 15 ms 23756 KB Ok
12 Correct 12 ms 23756 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 43368 KB Ok
2 Correct 126 ms 43484 KB Ok
3 Correct 126 ms 43300 KB Ok
4 Correct 128 ms 43284 KB Ok
5 Correct 124 ms 43332 KB Ok
6 Correct 126 ms 43588 KB Ok
7 Correct 138 ms 44416 KB Ok
8 Correct 134 ms 43788 KB Ok
9 Correct 140 ms 44592 KB Ok
10 Correct 133 ms 44024 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 43372 KB Ok
2 Correct 12 ms 23756 KB Ok
3 Correct 107 ms 43368 KB Ok
4 Correct 140 ms 43372 KB Ok
5 Correct 144 ms 43332 KB Ok
6 Correct 156 ms 43368 KB Ok
7 Correct 140 ms 43372 KB Ok
8 Correct 180 ms 43396 KB Ok
9 Correct 140 ms 43332 KB Ok
10 Correct 155 ms 43368 KB Ok
11 Correct 166 ms 43320 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 43368 KB Ok
2 Correct 206 ms 43460 KB Ok
3 Correct 213 ms 43368 KB Ok
4 Correct 205 ms 43364 KB Ok
5 Correct 226 ms 43332 KB Ok
6 Correct 639 ms 59976 KB Ok
7 Correct 497 ms 61364 KB Ok
8 Correct 922 ms 64404 KB Ok
9 Correct 644 ms 62544 KB Ok
10 Correct 460 ms 53972 KB Ok
11 Correct 692 ms 63988 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23800 KB Ok
2 Correct 13 ms 23756 KB Ok
3 Correct 12 ms 23756 KB Ok
4 Correct 13 ms 23756 KB Ok
5 Correct 12 ms 23756 KB Ok
6 Correct 12 ms 23756 KB Ok
7 Correct 12 ms 23756 KB Ok
8 Correct 12 ms 23756 KB Ok
9 Correct 14 ms 23756 KB Ok
10 Correct 13 ms 23756 KB Ok
11 Correct 15 ms 23756 KB Ok
12 Correct 12 ms 23756 KB Ok
13 Correct 58 ms 43372 KB Ok
14 Correct 12 ms 23756 KB Ok
15 Correct 107 ms 43368 KB Ok
16 Correct 140 ms 43372 KB Ok
17 Correct 144 ms 43332 KB Ok
18 Correct 156 ms 43368 KB Ok
19 Correct 140 ms 43372 KB Ok
20 Correct 180 ms 43396 KB Ok
21 Correct 140 ms 43332 KB Ok
22 Correct 155 ms 43368 KB Ok
23 Correct 166 ms 43320 KB Ok
24 Correct 96 ms 43412 KB Ok
25 Correct 119 ms 43484 KB Ok
26 Correct 112 ms 43400 KB Ok
27 Correct 127 ms 43460 KB Ok
28 Correct 112 ms 43472 KB Ok
29 Correct 78 ms 43452 KB Ok
30 Correct 114 ms 43380 KB Ok
31 Correct 146 ms 43500 KB Ok
32 Correct 144 ms 43388 KB Ok
33 Correct 123 ms 43460 KB Ok
34 Correct 222 ms 43796 KB Ok
35 Correct 218 ms 43744 KB Ok
36 Correct 223 ms 43824 KB Ok
37 Correct 228 ms 43796 KB Ok
38 Correct 200 ms 43848 KB Ok
39 Correct 220 ms 43844 KB Ok
40 Correct 225 ms 43860 KB Ok
41 Correct 213 ms 43852 KB Ok
42 Correct 221 ms 43796 KB Ok
43 Correct 224 ms 43828 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23800 KB Ok
2 Correct 13 ms 23756 KB Ok
3 Correct 12 ms 23756 KB Ok
4 Correct 13 ms 23756 KB Ok
5 Correct 12 ms 23756 KB Ok
6 Correct 12 ms 23756 KB Ok
7 Correct 12 ms 23756 KB Ok
8 Correct 12 ms 23756 KB Ok
9 Correct 14 ms 23756 KB Ok
10 Correct 13 ms 23756 KB Ok
11 Correct 15 ms 23756 KB Ok
12 Correct 12 ms 23756 KB Ok
13 Correct 122 ms 43368 KB Ok
14 Correct 126 ms 43484 KB Ok
15 Correct 126 ms 43300 KB Ok
16 Correct 128 ms 43284 KB Ok
17 Correct 124 ms 43332 KB Ok
18 Correct 126 ms 43588 KB Ok
19 Correct 138 ms 44416 KB Ok
20 Correct 134 ms 43788 KB Ok
21 Correct 140 ms 44592 KB Ok
22 Correct 133 ms 44024 KB Ok
23 Correct 58 ms 43372 KB Ok
24 Correct 12 ms 23756 KB Ok
25 Correct 107 ms 43368 KB Ok
26 Correct 140 ms 43372 KB Ok
27 Correct 144 ms 43332 KB Ok
28 Correct 156 ms 43368 KB Ok
29 Correct 140 ms 43372 KB Ok
30 Correct 180 ms 43396 KB Ok
31 Correct 140 ms 43332 KB Ok
32 Correct 155 ms 43368 KB Ok
33 Correct 166 ms 43320 KB Ok
34 Correct 96 ms 43412 KB Ok
35 Correct 119 ms 43484 KB Ok
36 Correct 112 ms 43400 KB Ok
37 Correct 127 ms 43460 KB Ok
38 Correct 112 ms 43472 KB Ok
39 Correct 78 ms 43452 KB Ok
40 Correct 114 ms 43380 KB Ok
41 Correct 146 ms 43500 KB Ok
42 Correct 144 ms 43388 KB Ok
43 Correct 123 ms 43460 KB Ok
44 Correct 222 ms 43796 KB Ok
45 Correct 218 ms 43744 KB Ok
46 Correct 223 ms 43824 KB Ok
47 Correct 228 ms 43796 KB Ok
48 Correct 200 ms 43848 KB Ok
49 Correct 220 ms 43844 KB Ok
50 Correct 225 ms 43860 KB Ok
51 Correct 213 ms 43852 KB Ok
52 Correct 221 ms 43796 KB Ok
53 Correct 224 ms 43828 KB Ok
54 Correct 449 ms 47180 KB Ok
55 Correct 552 ms 47648 KB Ok
56 Correct 503 ms 47948 KB Ok
57 Correct 336 ms 46528 KB Ok
58 Correct 471 ms 47228 KB Ok
59 Correct 430 ms 46928 KB Ok
60 Correct 331 ms 46468 KB Ok
61 Correct 387 ms 46668 KB Ok
62 Correct 573 ms 47488 KB Ok
63 Correct 374 ms 46768 KB Ok
64 Correct 521 ms 47492 KB Ok
65 Correct 482 ms 47644 KB Ok
66 Correct 422 ms 47004 KB Ok
67 Correct 328 ms 46956 KB Ok
68 Correct 460 ms 47044 KB Ok
69 Correct 1102 ms 57724 KB Ok
70 Correct 1115 ms 58068 KB Ok
71 Correct 1200 ms 58032 KB Ok
72 Correct 943 ms 57500 KB Ok
73 Correct 1186 ms 57896 KB Ok
74 Correct 1118 ms 58044 KB Ok
75 Correct 1109 ms 57916 KB Ok
76 Correct 1043 ms 57788 KB Ok
77 Correct 1127 ms 57728 KB Ok
78 Correct 1193 ms 57448 KB Ok
79 Correct 1232 ms 57840 KB Ok
80 Correct 1020 ms 58224 KB Ok
81 Correct 1104 ms 57916 KB Ok
82 Correct 1164 ms 57788 KB Ok
83 Correct 1090 ms 57864 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23800 KB Ok
2 Correct 13 ms 23756 KB Ok
3 Correct 12 ms 23756 KB Ok
4 Correct 13 ms 23756 KB Ok
5 Correct 12 ms 23756 KB Ok
6 Correct 12 ms 23756 KB Ok
7 Correct 12 ms 23756 KB Ok
8 Correct 12 ms 23756 KB Ok
9 Correct 14 ms 23756 KB Ok
10 Correct 13 ms 23756 KB Ok
11 Correct 15 ms 23756 KB Ok
12 Correct 12 ms 23756 KB Ok
13 Correct 122 ms 43368 KB Ok
14 Correct 126 ms 43484 KB Ok
15 Correct 126 ms 43300 KB Ok
16 Correct 128 ms 43284 KB Ok
17 Correct 124 ms 43332 KB Ok
18 Correct 126 ms 43588 KB Ok
19 Correct 138 ms 44416 KB Ok
20 Correct 134 ms 43788 KB Ok
21 Correct 140 ms 44592 KB Ok
22 Correct 133 ms 44024 KB Ok
23 Correct 58 ms 43372 KB Ok
24 Correct 12 ms 23756 KB Ok
25 Correct 107 ms 43368 KB Ok
26 Correct 140 ms 43372 KB Ok
27 Correct 144 ms 43332 KB Ok
28 Correct 156 ms 43368 KB Ok
29 Correct 140 ms 43372 KB Ok
30 Correct 180 ms 43396 KB Ok
31 Correct 140 ms 43332 KB Ok
32 Correct 155 ms 43368 KB Ok
33 Correct 166 ms 43320 KB Ok
34 Correct 201 ms 43368 KB Ok
35 Correct 206 ms 43460 KB Ok
36 Correct 213 ms 43368 KB Ok
37 Correct 205 ms 43364 KB Ok
38 Correct 226 ms 43332 KB Ok
39 Correct 639 ms 59976 KB Ok
40 Correct 497 ms 61364 KB Ok
41 Correct 922 ms 64404 KB Ok
42 Correct 644 ms 62544 KB Ok
43 Correct 460 ms 53972 KB Ok
44 Correct 692 ms 63988 KB Ok
45 Correct 96 ms 43412 KB Ok
46 Correct 119 ms 43484 KB Ok
47 Correct 112 ms 43400 KB Ok
48 Correct 127 ms 43460 KB Ok
49 Correct 112 ms 43472 KB Ok
50 Correct 78 ms 43452 KB Ok
51 Correct 114 ms 43380 KB Ok
52 Correct 146 ms 43500 KB Ok
53 Correct 144 ms 43388 KB Ok
54 Correct 123 ms 43460 KB Ok
55 Correct 222 ms 43796 KB Ok
56 Correct 218 ms 43744 KB Ok
57 Correct 223 ms 43824 KB Ok
58 Correct 228 ms 43796 KB Ok
59 Correct 200 ms 43848 KB Ok
60 Correct 220 ms 43844 KB Ok
61 Correct 225 ms 43860 KB Ok
62 Correct 213 ms 43852 KB Ok
63 Correct 221 ms 43796 KB Ok
64 Correct 224 ms 43828 KB Ok
65 Correct 449 ms 47180 KB Ok
66 Correct 552 ms 47648 KB Ok
67 Correct 503 ms 47948 KB Ok
68 Correct 336 ms 46528 KB Ok
69 Correct 471 ms 47228 KB Ok
70 Correct 430 ms 46928 KB Ok
71 Correct 331 ms 46468 KB Ok
72 Correct 387 ms 46668 KB Ok
73 Correct 573 ms 47488 KB Ok
74 Correct 374 ms 46768 KB Ok
75 Correct 521 ms 47492 KB Ok
76 Correct 482 ms 47644 KB Ok
77 Correct 422 ms 47004 KB Ok
78 Correct 328 ms 46956 KB Ok
79 Correct 460 ms 47044 KB Ok
80 Correct 1102 ms 57724 KB Ok
81 Correct 1115 ms 58068 KB Ok
82 Correct 1200 ms 58032 KB Ok
83 Correct 943 ms 57500 KB Ok
84 Correct 1186 ms 57896 KB Ok
85 Correct 1118 ms 58044 KB Ok
86 Correct 1109 ms 57916 KB Ok
87 Correct 1043 ms 57788 KB Ok
88 Correct 1127 ms 57728 KB Ok
89 Correct 1193 ms 57448 KB Ok
90 Correct 1232 ms 57840 KB Ok
91 Correct 1020 ms 58224 KB Ok
92 Correct 1104 ms 57916 KB Ok
93 Correct 1164 ms 57788 KB Ok
94 Correct 1090 ms 57864 KB Ok
95 Correct 742 ms 53320 KB Ok
96 Correct 1445 ms 58104 KB Ok
97 Correct 1400 ms 56508 KB Ok
98 Correct 719 ms 54280 KB Ok
99 Correct 987 ms 55936 KB Ok
100 Correct 1374 ms 56112 KB Ok
101 Correct 1289 ms 56084 KB Ok
102 Correct 1300 ms 55944 KB Ok
103 Correct 1518 ms 56884 KB Ok
104 Correct 1676 ms 57448 KB Ok
105 Correct 1392 ms 57460 KB Ok
106 Correct 1213 ms 56444 KB Ok
107 Correct 1124 ms 56048 KB Ok
108 Correct 1720 ms 57164 KB Ok
109 Correct 1289 ms 57776 KB Ok
110 Execution timed out 2090 ms 68400 KB Time limit exceeded
111 Halted 0 ms 0 KB -