oj.uz

Submission #519354

# Submission time Handle Problem Language Result Execution time Memory
519354 2022-01-26T08:54:43 Z Dasha_Gnedko Nice sequence (IZhO18_sequence) C++17
76 / 100
 1183 ms 61468 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];

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);
    }
}

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;
    int start = len;
    for(int i = 0; i <= len; i++)
    {
        if (!can[i]) continue;
        DFS(i, start);
        start += len;
    }
    if (fl) return 0;
    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 23756 KB Ok
2 Correct 12 ms 23812 KB Ok
3 Correct 11 ms 23756 KB Ok
4 Correct 12 ms 23764 KB Ok
5 Correct 12 ms 23712 KB Ok
6 Correct 13 ms 23808 KB Ok
7 Correct 14 ms 23756 KB Ok
8 Correct 15 ms 23812 KB Ok
9 Correct 14 ms 23692 KB Ok
10 Correct 12 ms 23756 KB Ok
11 Correct 12 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 124 ms 43340 KB Ok
2 Correct 128 ms 43272 KB Ok
3 Correct 159 ms 43372 KB Ok
4 Correct 121 ms 43332 KB Ok
5 Correct 126 ms 43372 KB Ok
6 Correct 138 ms 43544 KB Ok
7 Correct 140 ms 44268 KB Ok
8 Correct 123 ms 43720 KB Ok
9 Correct 140 ms 44388 KB Ok
10 Correct 129 ms 43988 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 43332 KB Ok
2 Correct 12 ms 23756 KB Ok
3 Correct 109 ms 43364 KB Ok
4 Correct 141 ms 43344 KB Ok
5 Correct 142 ms 43352 KB Ok
6 Correct 161 ms 43380 KB Ok
7 Correct 149 ms 43308 KB Ok
8 Correct 171 ms 43380 KB Ok
9 Correct 141 ms 43492 KB Ok
10 Correct 159 ms 43460 KB Ok
11 Correct 154 ms 43384 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 43256 KB Ok
2 Correct 215 ms 43288 KB Ok
3 Correct 198 ms 43256 KB Ok
4 Correct 208 ms 43376 KB Ok
5 Correct 261 ms 43336 KB Ok
6 Correct 593 ms 57528 KB Ok
7 Correct 472 ms 57480 KB Ok
8 Correct 862 ms 61468 KB Ok
9 Correct 578 ms 59724 KB Ok
10 Correct 415 ms 52212 KB Ok
11 Correct 657 ms 60792 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Ok
2 Correct 12 ms 23812 KB Ok
3 Correct 11 ms 23756 KB Ok
4 Correct 12 ms 23764 KB Ok
5 Correct 12 ms 23712 KB Ok
6 Correct 13 ms 23808 KB Ok
7 Correct 14 ms 23756 KB Ok
8 Correct 15 ms 23812 KB Ok
9 Correct 14 ms 23692 KB Ok
10 Correct 12 ms 23756 KB Ok
11 Correct 12 ms 23756 KB Ok
12 Correct 12 ms 23756 KB Ok
13 Correct 57 ms 43332 KB Ok
14 Correct 12 ms 23756 KB Ok
15 Correct 109 ms 43364 KB Ok
16 Correct 141 ms 43344 KB Ok
17 Correct 142 ms 43352 KB Ok
18 Correct 161 ms 43380 KB Ok
19 Correct 149 ms 43308 KB Ok
20 Correct 171 ms 43380 KB Ok
21 Correct 141 ms 43492 KB Ok
22 Correct 159 ms 43460 KB Ok
23 Correct 154 ms 43384 KB Ok
24 Correct 99 ms 43392 KB Ok
25 Correct 116 ms 43484 KB Ok
26 Correct 108 ms 43412 KB Ok
27 Correct 135 ms 43496 KB Ok
28 Correct 113 ms 43416 KB Ok
29 Correct 75 ms 43424 KB Ok
30 Correct 112 ms 43472 KB Ok
31 Correct 145 ms 43460 KB Ok
32 Correct 147 ms 43448 KB Ok
33 Correct 130 ms 43492 KB Ok
34 Correct 241 ms 43680 KB Ok
35 Correct 222 ms 43720 KB Ok
36 Correct 242 ms 43748 KB Ok
37 Correct 215 ms 43792 KB Ok
38 Correct 227 ms 43736 KB Ok
39 Correct 226 ms 43672 KB Ok
40 Correct 239 ms 43728 KB Ok
41 Correct 216 ms 43724 KB Ok
42 Correct 232 ms 43992 KB Ok
43 Correct 234 ms 43756 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Ok
2 Correct 12 ms 23812 KB Ok
3 Correct 11 ms 23756 KB Ok
4 Correct 12 ms 23764 KB Ok
5 Correct 12 ms 23712 KB Ok
6 Correct 13 ms 23808 KB Ok
7 Correct 14 ms 23756 KB Ok
8 Correct 15 ms 23812 KB Ok
9 Correct 14 ms 23692 KB Ok
10 Correct 12 ms 23756 KB Ok
11 Correct 12 ms 23756 KB Ok
12 Correct 12 ms 23756 KB Ok
13 Correct 124 ms 43340 KB Ok
14 Correct 128 ms 43272 KB Ok
15 Correct 159 ms 43372 KB Ok
16 Correct 121 ms 43332 KB Ok
17 Correct 126 ms 43372 KB Ok
18 Correct 138 ms 43544 KB Ok
19 Correct 140 ms 44268 KB Ok
20 Correct 123 ms 43720 KB Ok
21 Correct 140 ms 44388 KB Ok
22 Correct 129 ms 43988 KB Ok
23 Correct 57 ms 43332 KB Ok
24 Correct 12 ms 23756 KB Ok
25 Correct 109 ms 43364 KB Ok
26 Correct 141 ms 43344 KB Ok
27 Correct 142 ms 43352 KB Ok
28 Correct 161 ms 43380 KB Ok
29 Correct 149 ms 43308 KB Ok
30 Correct 171 ms 43380 KB Ok
31 Correct 141 ms 43492 KB Ok
32 Correct 159 ms 43460 KB Ok
33 Correct 154 ms 43384 KB Ok
34 Correct 99 ms 43392 KB Ok
35 Correct 116 ms 43484 KB Ok
36 Correct 108 ms 43412 KB Ok
37 Correct 135 ms 43496 KB Ok
38 Correct 113 ms 43416 KB Ok
39 Correct 75 ms 43424 KB Ok
40 Correct 112 ms 43472 KB Ok
41 Correct 145 ms 43460 KB Ok
42 Correct 147 ms 43448 KB Ok
43 Correct 130 ms 43492 KB Ok
44 Correct 241 ms 43680 KB Ok
45 Correct 222 ms 43720 KB Ok
46 Correct 242 ms 43748 KB Ok
47 Correct 215 ms 43792 KB Ok
48 Correct 227 ms 43736 KB Ok
49 Correct 226 ms 43672 KB Ok
50 Correct 239 ms 43728 KB Ok
51 Correct 216 ms 43724 KB Ok
52 Correct 232 ms 43992 KB Ok
53 Correct 234 ms 43756 KB Ok
54 Correct 389 ms 48416 KB Ok
55 Correct 529 ms 49588 KB Ok
56 Correct 492 ms 49452 KB Ok
57 Correct 314 ms 47872 KB Ok
58 Correct 451 ms 48828 KB Ok
59 Correct 410 ms 48240 KB Ok
60 Correct 303 ms 47476 KB Ok
61 Correct 329 ms 47936 KB Ok
62 Correct 529 ms 49460 KB Ok
63 Correct 344 ms 47984 KB Ok
64 Correct 467 ms 49228 KB Ok
65 Correct 432 ms 49048 KB Ok
66 Correct 368 ms 48336 KB Ok
67 Correct 286 ms 47676 KB Ok
68 Correct 408 ms 48484 KB Ok
69 Correct 1094 ms 55852 KB Ok
70 Correct 1073 ms 56164 KB Ok
71 Correct 1119 ms 56124 KB Ok
72 Correct 921 ms 55608 KB Ok
73 Correct 1137 ms 56168 KB Ok
74 Correct 1060 ms 56160 KB Ok
75 Correct 1093 ms 56016 KB Ok
76 Correct 1084 ms 55856 KB Ok
77 Correct 1140 ms 56132 KB Ok
78 Correct 1067 ms 55484 KB Ok
79 Correct 1183 ms 56292 KB Ok
80 Correct 956 ms 56308 KB Ok
81 Correct 1025 ms 56056 KB Ok
82 Correct 1109 ms 56080 KB Ok
83 Correct 1030 ms 56004 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Ok
2 Correct 12 ms 23812 KB Ok
3 Correct 11 ms 23756 KB Ok
4 Correct 12 ms 23764 KB Ok
5 Correct 12 ms 23712 KB Ok
6 Correct 13 ms 23808 KB Ok
7 Correct 14 ms 23756 KB Ok
8 Correct 15 ms 23812 KB Ok
9 Correct 14 ms 23692 KB Ok
10 Correct 12 ms 23756 KB Ok
11 Correct 12 ms 23756 KB Ok
12 Correct 12 ms 23756 KB Ok
13 Correct 124 ms 43340 KB Ok
14 Correct 128 ms 43272 KB Ok
15 Correct 159 ms 43372 KB Ok
16 Correct 121 ms 43332 KB Ok
17 Correct 126 ms 43372 KB Ok
18 Correct 138 ms 43544 KB Ok
19 Correct 140 ms 44268 KB Ok
20 Correct 123 ms 43720 KB Ok
21 Correct 140 ms 44388 KB Ok
22 Correct 129 ms 43988 KB Ok
23 Correct 57 ms 43332 KB Ok
24 Correct 12 ms 23756 KB Ok
25 Correct 109 ms 43364 KB Ok
26 Correct 141 ms 43344 KB Ok
27 Correct 142 ms 43352 KB Ok
28 Correct 161 ms 43380 KB Ok
29 Correct 149 ms 43308 KB Ok
30 Correct 171 ms 43380 KB Ok
31 Correct 141 ms 43492 KB Ok
32 Correct 159 ms 43460 KB Ok
33 Correct 154 ms 43384 KB Ok
34 Correct 189 ms 43256 KB Ok
35 Correct 215 ms 43288 KB Ok
36 Correct 198 ms 43256 KB Ok
37 Correct 208 ms 43376 KB Ok
38 Correct 261 ms 43336 KB Ok
39 Correct 593 ms 57528 KB Ok
40 Correct 472 ms 57480 KB Ok
41 Correct 862 ms 61468 KB Ok
42 Correct 578 ms 59724 KB Ok
43 Correct 415 ms 52212 KB Ok
44 Correct 657 ms 60792 KB Ok
45 Correct 99 ms 43392 KB Ok
46 Correct 116 ms 43484 KB Ok
47 Correct 108 ms 43412 KB Ok
48 Correct 135 ms 43496 KB Ok
49 Correct 113 ms 43416 KB Ok
50 Correct 75 ms 43424 KB Ok
51 Correct 112 ms 43472 KB Ok
52 Correct 145 ms 43460 KB Ok
53 Correct 147 ms 43448 KB Ok
54 Correct 130 ms 43492 KB Ok
55 Correct 241 ms 43680 KB Ok
56 Correct 222 ms 43720 KB Ok
57 Correct 242 ms 43748 KB Ok
58 Correct 215 ms 43792 KB Ok
59 Correct 227 ms 43736 KB Ok
60 Correct 226 ms 43672 KB Ok
61 Correct 239 ms 43728 KB Ok
62 Correct 216 ms 43724 KB Ok
63 Correct 232 ms 43992 KB Ok
64 Correct 234 ms 43756 KB Ok
65 Correct 389 ms 48416 KB Ok
66 Correct 529 ms 49588 KB Ok
67 Correct 492 ms 49452 KB Ok
68 Correct 314 ms 47872 KB Ok
69 Correct 451 ms 48828 KB Ok
70 Correct 410 ms 48240 KB Ok
71 Correct 303 ms 47476 KB Ok
72 Correct 329 ms 47936 KB Ok
73 Correct 529 ms 49460 KB Ok
74 Correct 344 ms 47984 KB Ok
75 Correct 467 ms 49228 KB Ok
76 Correct 432 ms 49048 KB Ok
77 Correct 368 ms 48336 KB Ok
78 Correct 286 ms 47676 KB Ok
79 Correct 408 ms 48484 KB Ok
80 Correct 1094 ms 55852 KB Ok
81 Correct 1073 ms 56164 KB Ok
82 Correct 1119 ms 56124 KB Ok
83 Correct 921 ms 55608 KB Ok
84 Correct 1137 ms 56168 KB Ok
85 Correct 1060 ms 56160 KB Ok
86 Correct 1093 ms 56016 KB Ok
87 Correct 1084 ms 55856 KB Ok
88 Correct 1140 ms 56132 KB Ok
89 Correct 1067 ms 55484 KB Ok
90 Correct 1183 ms 56292 KB Ok
91 Correct 956 ms 56308 KB Ok
92 Correct 1025 ms 56056 KB Ok
93 Correct 1109 ms 56080 KB Ok
94 Correct 1030 ms 56004 KB Ok
95 Incorrect 686 ms 55212 KB Absolute value of 2100010814 bigger than 1000000
96 Halted 0 ms 0 KB -