oj.uz

Submission #519351

# Submission time Handle Problem Language Result Execution time Memory
519351 2022-01-26T08:52:46 Z Dasha_Gnedko Nice sequence (IZhO18_sequence) C++17
15 / 100
 199 ms 44388 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;
    for(int i = 0; i <= len; i++)
    {
        if (!can[i]) continue;
        DFS(i, 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 14 ms 23796 KB Ok
2 Correct 13 ms 23756 KB Ok
3 Correct 11 ms 23740 KB Ok
4 Correct 16 ms 23812 KB Ok
5 Correct 12 ms 23756 KB Ok
6 Correct 12 ms 23712 KB Ok
7 Correct 12 ms 23720 KB Ok
8 Correct 10 ms 23780 KB Ok
9 Correct 10 ms 23800 KB Ok
10 Correct 10 ms 23692 KB Ok
11 Correct 15 ms 23712 KB Ok
12 Correct 11 ms 23716 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 43376 KB Ok
2 Correct 119 ms 43384 KB Ok
3 Correct 128 ms 43384 KB Ok
4 Correct 144 ms 43376 KB Ok
5 Correct 126 ms 43316 KB Ok
6 Correct 136 ms 43516 KB Ok
7 Correct 160 ms 44320 KB Ok
8 Correct 142 ms 43716 KB Ok
9 Correct 142 ms 44388 KB Ok
10 Correct 142 ms 43976 KB Ok

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 43292 KB Ok
2 Correct 13 ms 23800 KB Ok
3 Correct 118 ms 43364 KB Ok
4 Correct 150 ms 43376 KB Ok
5 Incorrect 158 ms 43380 KB All the numbers must be nonzero
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 199 ms 43380 KB All the numbers must be nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23796 KB Ok
2 Correct 13 ms 23756 KB Ok
3 Correct 11 ms 23740 KB Ok
4 Correct 16 ms 23812 KB Ok
5 Correct 12 ms 23756 KB Ok
6 Correct 12 ms 23712 KB Ok
7 Correct 12 ms 23720 KB Ok
8 Correct 10 ms 23780 KB Ok
9 Correct 10 ms 23800 KB Ok
10 Correct 10 ms 23692 KB Ok
11 Correct 15 ms 23712 KB Ok
12 Correct 11 ms 23716 KB Ok
13 Correct 56 ms 43292 KB Ok
14 Correct 13 ms 23800 KB Ok
15 Correct 118 ms 43364 KB Ok
16 Correct 150 ms 43376 KB Ok
17 Incorrect 158 ms 43380 KB All the numbers must be nonzero
18 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23796 KB Ok
2 Correct 13 ms 23756 KB Ok
3 Correct 11 ms 23740 KB Ok
4 Correct 16 ms 23812 KB Ok
5 Correct 12 ms 23756 KB Ok
6 Correct 12 ms 23712 KB Ok
7 Correct 12 ms 23720 KB Ok
8 Correct 10 ms 23780 KB Ok
9 Correct 10 ms 23800 KB Ok
10 Correct 10 ms 23692 KB Ok
11 Correct 15 ms 23712 KB Ok
12 Correct 11 ms 23716 KB Ok
13 Correct 127 ms 43376 KB Ok
14 Correct 119 ms 43384 KB Ok
15 Correct 128 ms 43384 KB Ok
16 Correct 144 ms 43376 KB Ok
17 Correct 126 ms 43316 KB Ok
18 Correct 136 ms 43516 KB Ok
19 Correct 160 ms 44320 KB Ok
20 Correct 142 ms 43716 KB Ok
21 Correct 142 ms 44388 KB Ok
22 Correct 142 ms 43976 KB Ok
23 Correct 56 ms 43292 KB Ok
24 Correct 13 ms 23800 KB Ok
25 Correct 118 ms 43364 KB Ok
26 Correct 150 ms 43376 KB Ok
27 Incorrect 158 ms 43380 KB All the numbers must be nonzero
28 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23796 KB Ok
2 Correct 13 ms 23756 KB Ok
3 Correct 11 ms 23740 KB Ok
4 Correct 16 ms 23812 KB Ok
5 Correct 12 ms 23756 KB Ok
6 Correct 12 ms 23712 KB Ok
7 Correct 12 ms 23720 KB Ok
8 Correct 10 ms 23780 KB Ok
9 Correct 10 ms 23800 KB Ok
10 Correct 10 ms 23692 KB Ok
11 Correct 15 ms 23712 KB Ok
12 Correct 11 ms 23716 KB Ok
13 Correct 127 ms 43376 KB Ok
14 Correct 119 ms 43384 KB Ok
15 Correct 128 ms 43384 KB Ok
16 Correct 144 ms 43376 KB Ok
17 Correct 126 ms 43316 KB Ok
18 Correct 136 ms 43516 KB Ok
19 Correct 160 ms 44320 KB Ok
20 Correct 142 ms 43716 KB Ok
21 Correct 142 ms 44388 KB Ok
22 Correct 142 ms 43976 KB Ok
23 Correct 56 ms 43292 KB Ok
24 Correct 13 ms 23800 KB Ok
25 Correct 118 ms 43364 KB Ok
26 Correct 150 ms 43376 KB Ok
27 Incorrect 158 ms 43380 KB All the numbers must be nonzero
28 Halted 0 ms 0 KB -