oj.uz

Submission #737064

# Submission time Handle Problem Language Result Execution time Memory
737064 2023-05-06T14:15:10 Z GrindMachine Nice sequence (IZhO18_sequence) C++17
58 / 100
 2000 ms 71248 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<int> adj[N];
vector<bool> vis(N), recstack(N);
vector<int> topo;
bool cyc;

void dfs(int 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)
{
    int n, m; cin >> n >> m;

    auto ok = [&](int 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;
    };

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

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

    ok(ans);

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

    cout << ans << endl;

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

    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<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 431 ms 65356 KB Ok
2 Correct 476 ms 65344 KB Ok
3 Correct 583 ms 43516 KB Ok
4 Correct 514 ms 45088 KB Ok
5 Correct 642 ms 43564 KB Ok
6 Correct 432 ms 47580 KB Ok
7 Correct 492 ms 42916 KB Ok
8 Correct 460 ms 47680 KB Ok
9 Correct 511 ms 43344 KB Ok
10 Correct 474 ms 53500 KB Ok
11 Correct 524 ms 42952 KB Ok
12 Correct 483 ms 42428 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 65136 KB Ok
2 Correct 440 ms 65208 KB Ok
3 Correct 510 ms 65208 KB Ok
4 Correct 495 ms 65208 KB Ok
5 Correct 494 ms 65164 KB Ok
6 Correct 411 ms 65344 KB Ok
7 Correct 474 ms 65500 KB Ok
8 Correct 451 ms 65512 KB Ok
9 Correct 459 ms 65860 KB Ok
10 Correct 462 ms 65508 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 65260 KB Ok
2 Correct 439 ms 65312 KB Ok
3 Correct 445 ms 65172 KB Ok
4 Correct 458 ms 65256 KB Ok
5 Correct 471 ms 65340 KB Ok
6 Correct 454 ms 65212 KB Ok
7 Correct 449 ms 65348 KB Ok
8 Correct 450 ms 65288 KB Ok
9 Correct 481 ms 65208 KB Ok
10 Correct 496 ms 65208 KB Ok
11 Correct 440 ms 65136 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 65328 KB Ok
2 Correct 475 ms 65344 KB Ok
3 Correct 543 ms 65256 KB Ok
4 Correct 521 ms 65300 KB Ok
5 Correct 549 ms 65324 KB Ok
6 Correct 975 ms 69400 KB Ok
7 Correct 759 ms 67908 KB Ok
8 Correct 1262 ms 70580 KB Ok
9 Correct 992 ms 71248 KB Ok
10 Correct 731 ms 67956 KB Ok
11 Correct 1028 ms 70492 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 65356 KB Ok
2 Correct 476 ms 65344 KB Ok
3 Correct 583 ms 43516 KB Ok
4 Correct 514 ms 45088 KB Ok
5 Correct 642 ms 43564 KB Ok
6 Correct 432 ms 47580 KB Ok
7 Correct 492 ms 42916 KB Ok
8 Correct 460 ms 47680 KB Ok
9 Correct 511 ms 43344 KB Ok
10 Correct 474 ms 53500 KB Ok
11 Correct 524 ms 42952 KB Ok
12 Correct 483 ms 42428 KB Ok
13 Correct 177 ms 65260 KB Ok
14 Correct 439 ms 65312 KB Ok
15 Correct 445 ms 65172 KB Ok
16 Correct 458 ms 65256 KB Ok
17 Correct 471 ms 65340 KB Ok
18 Correct 454 ms 65212 KB Ok
19 Correct 449 ms 65348 KB Ok
20 Correct 450 ms 65288 KB Ok
21 Correct 481 ms 65208 KB Ok
22 Correct 496 ms 65208 KB Ok
23 Correct 440 ms 65136 KB Ok
24 Correct 655 ms 41972 KB Ok
25 Correct 727 ms 42244 KB Ok
26 Correct 665 ms 43476 KB Ok
27 Correct 830 ms 43628 KB Ok
28 Correct 673 ms 42252 KB Ok
29 Correct 653 ms 49796 KB Ok
30 Correct 648 ms 42952 KB Ok
31 Correct 708 ms 42256 KB Ok
32 Correct 694 ms 42096 KB Ok
33 Correct 736 ms 43236 KB Ok
34 Correct 1255 ms 65340 KB Ok
35 Correct 716 ms 65520 KB Ok
36 Correct 1108 ms 65380 KB Ok
37 Correct 813 ms 65384 KB Ok
38 Correct 817 ms 65312 KB Ok
39 Correct 1174 ms 65488 KB Ok
40 Correct 913 ms 65396 KB Ok
41 Correct 764 ms 65368 KB Ok
42 Correct 1235 ms 65392 KB Ok
43 Correct 949 ms 65488 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 65356 KB Ok
2 Correct 476 ms 65344 KB Ok
3 Correct 583 ms 43516 KB Ok
4 Correct 514 ms 45088 KB Ok
5 Correct 642 ms 43564 KB Ok
6 Correct 432 ms 47580 KB Ok
7 Correct 492 ms 42916 KB Ok
8 Correct 460 ms 47680 KB Ok
9 Correct 511 ms 43344 KB Ok
10 Correct 474 ms 53500 KB Ok
11 Correct 524 ms 42952 KB Ok
12 Correct 483 ms 42428 KB Ok
13 Correct 481 ms 65136 KB Ok
14 Correct 440 ms 65208 KB Ok
15 Correct 510 ms 65208 KB Ok
16 Correct 495 ms 65208 KB Ok
17 Correct 494 ms 65164 KB Ok
18 Correct 411 ms 65344 KB Ok
19 Correct 474 ms 65500 KB Ok
20 Correct 451 ms 65512 KB Ok
21 Correct 459 ms 65860 KB Ok
22 Correct 462 ms 65508 KB Ok
23 Correct 177 ms 65260 KB Ok
24 Correct 439 ms 65312 KB Ok
25 Correct 445 ms 65172 KB Ok
26 Correct 458 ms 65256 KB Ok
27 Correct 471 ms 65340 KB Ok
28 Correct 454 ms 65212 KB Ok
29 Correct 449 ms 65348 KB Ok
30 Correct 450 ms 65288 KB Ok
31 Correct 481 ms 65208 KB Ok
32 Correct 496 ms 65208 KB Ok
33 Correct 440 ms 65136 KB Ok
34 Correct 655 ms 41972 KB Ok
35 Correct 727 ms 42244 KB Ok
36 Correct 665 ms 43476 KB Ok
37 Correct 830 ms 43628 KB Ok
38 Correct 673 ms 42252 KB Ok
39 Correct 653 ms 49796 KB Ok
40 Correct 648 ms 42952 KB Ok
41 Correct 708 ms 42256 KB Ok
42 Correct 694 ms 42096 KB Ok
43 Correct 736 ms 43236 KB Ok
44 Correct 1255 ms 65340 KB Ok
45 Correct 716 ms 65520 KB Ok
46 Correct 1108 ms 65380 KB Ok
47 Correct 813 ms 65384 KB Ok
48 Correct 817 ms 65312 KB Ok
49 Correct 1174 ms 65488 KB Ok
50 Correct 913 ms 65396 KB Ok
51 Correct 764 ms 65368 KB Ok
52 Correct 1235 ms 65392 KB Ok
53 Correct 949 ms 65488 KB Ok
54 Correct 755 ms 44140 KB Ok
55 Correct 874 ms 44572 KB Ok
56 Correct 961 ms 44408 KB Ok
57 Correct 675 ms 43688 KB Ok
58 Correct 824 ms 44524 KB Ok
59 Correct 806 ms 44356 KB Ok
60 Correct 719 ms 43896 KB Ok
61 Correct 689 ms 43928 KB Ok
62 Correct 947 ms 44764 KB Ok
63 Correct 757 ms 44068 KB Ok
64 Correct 859 ms 44592 KB Ok
65 Correct 792 ms 44372 KB Ok
66 Correct 727 ms 44088 KB Ok
67 Correct 673 ms 43900 KB Ok
68 Correct 813 ms 44476 KB Ok
69 Execution timed out 2070 ms 69868 KB Time limit exceeded
70 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 65356 KB Ok
2 Correct 476 ms 65344 KB Ok
3 Correct 583 ms 43516 KB Ok
4 Correct 514 ms 45088 KB Ok
5 Correct 642 ms 43564 KB Ok
6 Correct 432 ms 47580 KB Ok
7 Correct 492 ms 42916 KB Ok
8 Correct 460 ms 47680 KB Ok
9 Correct 511 ms 43344 KB Ok
10 Correct 474 ms 53500 KB Ok
11 Correct 524 ms 42952 KB Ok
12 Correct 483 ms 42428 KB Ok
13 Correct 481 ms 65136 KB Ok
14 Correct 440 ms 65208 KB Ok
15 Correct 510 ms 65208 KB Ok
16 Correct 495 ms 65208 KB Ok
17 Correct 494 ms 65164 KB Ok
18 Correct 411 ms 65344 KB Ok
19 Correct 474 ms 65500 KB Ok
20 Correct 451 ms 65512 KB Ok
21 Correct 459 ms 65860 KB Ok
22 Correct 462 ms 65508 KB Ok
23 Correct 177 ms 65260 KB Ok
24 Correct 439 ms 65312 KB Ok
25 Correct 445 ms 65172 KB Ok
26 Correct 458 ms 65256 KB Ok
27 Correct 471 ms 65340 KB Ok
28 Correct 454 ms 65212 KB Ok
29 Correct 449 ms 65348 KB Ok
30 Correct 450 ms 65288 KB Ok
31 Correct 481 ms 65208 KB Ok
32 Correct 496 ms 65208 KB Ok
33 Correct 440 ms 65136 KB Ok
34 Correct 437 ms 65328 KB Ok
35 Correct 475 ms 65344 KB Ok
36 Correct 543 ms 65256 KB Ok
37 Correct 521 ms 65300 KB Ok
38 Correct 549 ms 65324 KB Ok
39 Correct 975 ms 69400 KB Ok
40 Correct 759 ms 67908 KB Ok
41 Correct 1262 ms 70580 KB Ok
42 Correct 992 ms 71248 KB Ok
43 Correct 731 ms 67956 KB Ok
44 Correct 1028 ms 70492 KB Ok
45 Correct 655 ms 41972 KB Ok
46 Correct 727 ms 42244 KB Ok
47 Correct 665 ms 43476 KB Ok
48 Correct 830 ms 43628 KB Ok
49 Correct 673 ms 42252 KB Ok
50 Correct 653 ms 49796 KB Ok
51 Correct 648 ms 42952 KB Ok
52 Correct 708 ms 42256 KB Ok
53 Correct 694 ms 42096 KB Ok
54 Correct 736 ms 43236 KB Ok
55 Correct 1255 ms 65340 KB Ok
56 Correct 716 ms 65520 KB Ok
57 Correct 1108 ms 65380 KB Ok
58 Correct 813 ms 65384 KB Ok
59 Correct 817 ms 65312 KB Ok
60 Correct 1174 ms 65488 KB Ok
61 Correct 913 ms 65396 KB Ok
62 Correct 764 ms 65368 KB Ok
63 Correct 1235 ms 65392 KB Ok
64 Correct 949 ms 65488 KB Ok
65 Correct 755 ms 44140 KB Ok
66 Correct 874 ms 44572 KB Ok
67 Correct 961 ms 44408 KB Ok
68 Correct 675 ms 43688 KB Ok
69 Correct 824 ms 44524 KB Ok
70 Correct 806 ms 44356 KB Ok
71 Correct 719 ms 43896 KB Ok
72 Correct 689 ms 43928 KB Ok
73 Correct 947 ms 44764 KB Ok
74 Correct 757 ms 44068 KB Ok
75 Correct 859 ms 44592 KB Ok
76 Correct 792 ms 44372 KB Ok
77 Correct 727 ms 44088 KB Ok
78 Correct 673 ms 43900 KB Ok
79 Correct 813 ms 44476 KB Ok
80 Execution timed out 2070 ms 69868 KB Time limit exceeded
81 Halted 0 ms 0 KB -