oj.uz

Submission #737060

# Submission time Handle Problem Language Result Execution time Memory
737060 2023-05-06T14:10:55 Z GrindMachine Nice sequence (IZhO18_sequence) C++17
58 / 100
 2000 ms 73924 KB 
// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
https://codeforces.com/blog/entry/63991?#comment-478025
https://oj.uz/submission/682671


p(i) = pref sum until i
p(i) - p(i-n) < 0 => p(i) < p(i-n)
p(i) - p(i-m) > 0 => p(i) > p(i-m)

find a valid p and the answer can be restored from this

how to find a valid p
the only condition on p is the inequalities that we have

create an array that satisfies given inequalities:
in such cases, think toposort

add edge u-->v if p(u) < p(v)

add edges: i-->i-n and i-m-->i

find toposort, and assign p(i) values in the order every index appears in the toposort

how to find max len seq?
=> if we can make a seq of length k, then we can also make a seq of len k-1

so we can b.s on max len

*/

const int MOD = 1e9 + 7;
const int N = 1e6 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

vector<ll> adj[N];
vector<bool> vis(N), recstack(N);
vector<ll> topo;
bool cyc;

void dfs(ll u) {
    vis[u] = 1;
    recstack[u] = 1;

    trav(v, adj[u]) {
        if (vis[v]) {
            if (recstack[v]) cyc = true;
            conts;
        }

        dfs(v);
    }

    topo.pb(u);
    recstack[u] = 0;
}

void solve(int test_case)
{
    ll n, m; cin >> n >> m;

    auto ok = [&](ll mid) {
        rep(i, mid + 1) adj[i].clear(), vis[i] = 0;

        rep1(i, mid) {
            if (i - n >= 0) {
                adj[i].pb(i - n);
            }

            if (i - m >= 0) {
                adj[i - m].pb(i);
            }
        }

        topo.clear();
        cyc = false;

        rep(i, mid + 1) {
            if (vis[i]) conts;
            dfs(i);
        }

        reverse(all(topo));

        if (cyc) return false;
        return true;
    };

    ll l = 1, r = N - 1;
    ll ans = 0;

    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (ok(mid)) {
            ans = mid;
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }

    ok(ans);

    vector<ll> p(ans + 5);
    rep(i, sz(topo)) {
        p[topo[i]] = i;
    }

    cout << ans << endl;

    rep1(i, ans) {
        ll v = p[i] - p[i - 1];
        cout << v << " ";
    }

    cout << endl;
}

int main()
{
    fastio;

    int t = 1;
    cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Compilation message

sequence.cpp: In function 'void solve(int)':
sequence.cpp:30:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 | #define rep(i, n) for(int i = 0; i < n; ++i)
      |                                    ^
sequence.cpp:158:5: note: in expansion of macro 'rep'
  158 |     rep(i, sz(topo)) {
      |     ^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 67412 KB Ok
2 Correct 490 ms 67412 KB Ok
3 Correct 585 ms 45488 KB Ok
4 Correct 506 ms 47000 KB Ok
5 Correct 661 ms 45412 KB Ok
6 Correct 454 ms 49524 KB Ok
7 Correct 511 ms 44848 KB Ok
8 Correct 450 ms 49804 KB Ok
9 Correct 476 ms 45404 KB Ok
10 Correct 447 ms 55472 KB Ok
11 Correct 514 ms 44912 KB Ok
12 Correct 444 ms 44352 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 67208 KB Ok
2 Correct 440 ms 67124 KB Ok
3 Correct 514 ms 67124 KB Ok
4 Correct 491 ms 67212 KB Ok
5 Correct 491 ms 67248 KB Ok
6 Correct 451 ms 67336 KB Ok
7 Correct 447 ms 67476 KB Ok
8 Correct 440 ms 67360 KB Ok
9 Correct 447 ms 67836 KB Ok
10 Correct 422 ms 67304 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 67388 KB Ok
2 Correct 433 ms 67296 KB Ok
3 Correct 461 ms 67248 KB Ok
4 Correct 434 ms 67460 KB Ok
5 Correct 426 ms 67388 KB Ok
6 Correct 469 ms 67160 KB Ok
7 Correct 470 ms 67416 KB Ok
8 Correct 451 ms 67372 KB Ok
9 Correct 479 ms 67140 KB Ok
10 Correct 458 ms 67188 KB Ok
11 Correct 455 ms 67148 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 67360 KB Ok
2 Correct 465 ms 67340 KB Ok
3 Correct 510 ms 67420 KB Ok
4 Correct 500 ms 67388 KB Ok
5 Correct 546 ms 67388 KB Ok
6 Correct 932 ms 71996 KB Ok
7 Correct 727 ms 70584 KB Ok
8 Correct 1198 ms 73396 KB Ok
9 Correct 903 ms 73924 KB Ok
10 Correct 672 ms 70320 KB Ok
11 Correct 998 ms 73344 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 67412 KB Ok
2 Correct 490 ms 67412 KB Ok
3 Correct 585 ms 45488 KB Ok
4 Correct 506 ms 47000 KB Ok
5 Correct 661 ms 45412 KB Ok
6 Correct 454 ms 49524 KB Ok
7 Correct 511 ms 44848 KB Ok
8 Correct 450 ms 49804 KB Ok
9 Correct 476 ms 45404 KB Ok
10 Correct 447 ms 55472 KB Ok
11 Correct 514 ms 44912 KB Ok
12 Correct 444 ms 44352 KB Ok
13 Correct 168 ms 67388 KB Ok
14 Correct 433 ms 67296 KB Ok
15 Correct 461 ms 67248 KB Ok
16 Correct 434 ms 67460 KB Ok
17 Correct 426 ms 67388 KB Ok
18 Correct 469 ms 67160 KB Ok
19 Correct 470 ms 67416 KB Ok
20 Correct 451 ms 67372 KB Ok
21 Correct 479 ms 67140 KB Ok
22 Correct 458 ms 67188 KB Ok
23 Correct 455 ms 67148 KB Ok
24 Correct 658 ms 43940 KB Ok
25 Correct 703 ms 44220 KB Ok
26 Correct 643 ms 45392 KB Ok
27 Correct 795 ms 45640 KB Ok
28 Correct 669 ms 44204 KB Ok
29 Correct 662 ms 51580 KB Ok
30 Correct 606 ms 44940 KB Ok
31 Correct 719 ms 44156 KB Ok
32 Correct 744 ms 44092 KB Ok
33 Correct 801 ms 45080 KB Ok
34 Correct 1346 ms 67320 KB Ok
35 Correct 795 ms 67308 KB Ok
36 Correct 1191 ms 67400 KB Ok
37 Correct 850 ms 67328 KB Ok
38 Correct 905 ms 67308 KB Ok
39 Correct 1403 ms 67324 KB Ok
40 Correct 1070 ms 67364 KB Ok
41 Correct 844 ms 67348 KB Ok
42 Correct 1346 ms 67276 KB Ok
43 Correct 947 ms 67308 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 67412 KB Ok
2 Correct 490 ms 67412 KB Ok
3 Correct 585 ms 45488 KB Ok
4 Correct 506 ms 47000 KB Ok
5 Correct 661 ms 45412 KB Ok
6 Correct 454 ms 49524 KB Ok
7 Correct 511 ms 44848 KB Ok
8 Correct 450 ms 49804 KB Ok
9 Correct 476 ms 45404 KB Ok
10 Correct 447 ms 55472 KB Ok
11 Correct 514 ms 44912 KB Ok
12 Correct 444 ms 44352 KB Ok
13 Correct 427 ms 67208 KB Ok
14 Correct 440 ms 67124 KB Ok
15 Correct 514 ms 67124 KB Ok
16 Correct 491 ms 67212 KB Ok
17 Correct 491 ms 67248 KB Ok
18 Correct 451 ms 67336 KB Ok
19 Correct 447 ms 67476 KB Ok
20 Correct 440 ms 67360 KB Ok
21 Correct 447 ms 67836 KB Ok
22 Correct 422 ms 67304 KB Ok
23 Correct 168 ms 67388 KB Ok
24 Correct 433 ms 67296 KB Ok
25 Correct 461 ms 67248 KB Ok
26 Correct 434 ms 67460 KB Ok
27 Correct 426 ms 67388 KB Ok
28 Correct 469 ms 67160 KB Ok
29 Correct 470 ms 67416 KB Ok
30 Correct 451 ms 67372 KB Ok
31 Correct 479 ms 67140 KB Ok
32 Correct 458 ms 67188 KB Ok
33 Correct 455 ms 67148 KB Ok
34 Correct 658 ms 43940 KB Ok
35 Correct 703 ms 44220 KB Ok
36 Correct 643 ms 45392 KB Ok
37 Correct 795 ms 45640 KB Ok
38 Correct 669 ms 44204 KB Ok
39 Correct 662 ms 51580 KB Ok
40 Correct 606 ms 44940 KB Ok
41 Correct 719 ms 44156 KB Ok
42 Correct 744 ms 44092 KB Ok
43 Correct 801 ms 45080 KB Ok
44 Correct 1346 ms 67320 KB Ok
45 Correct 795 ms 67308 KB Ok
46 Correct 1191 ms 67400 KB Ok
47 Correct 850 ms 67328 KB Ok
48 Correct 905 ms 67308 KB Ok
49 Correct 1403 ms 67324 KB Ok
50 Correct 1070 ms 67364 KB Ok
51 Correct 844 ms 67348 KB Ok
52 Correct 1346 ms 67276 KB Ok
53 Correct 947 ms 67308 KB Ok
54 Correct 850 ms 46472 KB Ok
55 Correct 898 ms 46888 KB Ok
56 Correct 1042 ms 46860 KB Ok
57 Correct 708 ms 45992 KB Ok
58 Correct 866 ms 46680 KB Ok
59 Correct 852 ms 46528 KB Ok
60 Correct 735 ms 46240 KB Ok
61 Correct 671 ms 46252 KB Ok
62 Correct 858 ms 47140 KB Ok
63 Correct 727 ms 46428 KB Ok
64 Correct 860 ms 46968 KB Ok
65 Correct 831 ms 46756 KB Ok
66 Correct 688 ms 46348 KB Ok
67 Correct 642 ms 46176 KB Ok
68 Correct 771 ms 46652 KB Ok
69 Execution timed out 2045 ms 71756 KB Time limit exceeded
70 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 67412 KB Ok
2 Correct 490 ms 67412 KB Ok
3 Correct 585 ms 45488 KB Ok
4 Correct 506 ms 47000 KB Ok
5 Correct 661 ms 45412 KB Ok
6 Correct 454 ms 49524 KB Ok
7 Correct 511 ms 44848 KB Ok
8 Correct 450 ms 49804 KB Ok
9 Correct 476 ms 45404 KB Ok
10 Correct 447 ms 55472 KB Ok
11 Correct 514 ms 44912 KB Ok
12 Correct 444 ms 44352 KB Ok
13 Correct 427 ms 67208 KB Ok
14 Correct 440 ms 67124 KB Ok
15 Correct 514 ms 67124 KB Ok
16 Correct 491 ms 67212 KB Ok
17 Correct 491 ms 67248 KB Ok
18 Correct 451 ms 67336 KB Ok
19 Correct 447 ms 67476 KB Ok
20 Correct 440 ms 67360 KB Ok
21 Correct 447 ms 67836 KB Ok
22 Correct 422 ms 67304 KB Ok
23 Correct 168 ms 67388 KB Ok
24 Correct 433 ms 67296 KB Ok
25 Correct 461 ms 67248 KB Ok
26 Correct 434 ms 67460 KB Ok
27 Correct 426 ms 67388 KB Ok
28 Correct 469 ms 67160 KB Ok
29 Correct 470 ms 67416 KB Ok
30 Correct 451 ms 67372 KB Ok
31 Correct 479 ms 67140 KB Ok
32 Correct 458 ms 67188 KB Ok
33 Correct 455 ms 67148 KB Ok
34 Correct 446 ms 67360 KB Ok
35 Correct 465 ms 67340 KB Ok
36 Correct 510 ms 67420 KB Ok
37 Correct 500 ms 67388 KB Ok
38 Correct 546 ms 67388 KB Ok
39 Correct 932 ms 71996 KB Ok
40 Correct 727 ms 70584 KB Ok
41 Correct 1198 ms 73396 KB Ok
42 Correct 903 ms 73924 KB Ok
43 Correct 672 ms 70320 KB Ok
44 Correct 998 ms 73344 KB Ok
45 Correct 658 ms 43940 KB Ok
46 Correct 703 ms 44220 KB Ok
47 Correct 643 ms 45392 KB Ok
48 Correct 795 ms 45640 KB Ok
49 Correct 669 ms 44204 KB Ok
50 Correct 662 ms 51580 KB Ok
51 Correct 606 ms 44940 KB Ok
52 Correct 719 ms 44156 KB Ok
53 Correct 744 ms 44092 KB Ok
54 Correct 801 ms 45080 KB Ok
55 Correct 1346 ms 67320 KB Ok
56 Correct 795 ms 67308 KB Ok
57 Correct 1191 ms 67400 KB Ok
58 Correct 850 ms 67328 KB Ok
59 Correct 905 ms 67308 KB Ok
60 Correct 1403 ms 67324 KB Ok
61 Correct 1070 ms 67364 KB Ok
62 Correct 844 ms 67348 KB Ok
63 Correct 1346 ms 67276 KB Ok
64 Correct 947 ms 67308 KB Ok
65 Correct 850 ms 46472 KB Ok
66 Correct 898 ms 46888 KB Ok
67 Correct 1042 ms 46860 KB Ok
68 Correct 708 ms 45992 KB Ok
69 Correct 866 ms 46680 KB Ok
70 Correct 852 ms 46528 KB Ok
71 Correct 735 ms 46240 KB Ok
72 Correct 671 ms 46252 KB Ok
73 Correct 858 ms 47140 KB Ok
74 Correct 727 ms 46428 KB Ok
75 Correct 860 ms 46968 KB Ok
76 Correct 831 ms 46756 KB Ok
77 Correct 688 ms 46348 KB Ok
78 Correct 642 ms 46176 KB Ok
79 Correct 771 ms 46652 KB Ok
80 Execution timed out 2045 ms 71756 KB Time limit exceeded
81 Halted 0 ms 0 KB -