oj.uz

Submission #737069

# Submission time Handle Problem Language Result Execution time Memory
737069 2023-05-06T14:26:03 Z GrindMachine Nice sequence (IZhO18_sequence) C++17
100 / 100
 1643 ms 57416 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<bool> vis(N), recstack(N);
vector<int> topo;
bool cyc;
int n, m, k;

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

    for (auto v : {u - n, u + m}) {
        if (v < 0 or v > k) conts;

        if (vis[v]) {
            if (recstack[v]) cyc = true;
            conts;
        }

        dfs(v);
    }

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

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

    auto ok = [&](int mid) {
        k = mid;
        rep(i, k + 1) vis[i] = 0;

        topo.clear();
        cyc = false;

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

        reverse(all(topo));

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

    int l = 1, r = n + m;
    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:151:5: note: in expansion of macro 'rep'
  151 |     rep(i, sz(topo)) {
      |     ^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Ok
2 Correct 1 ms 564 KB Ok
3 Correct 1 ms 568 KB Ok
4 Correct 1 ms 468 KB Ok
5 Correct 1 ms 468 KB Ok
6 Correct 1 ms 468 KB Ok
7 Correct 1 ms 560 KB Ok
8 Correct 1 ms 468 KB Ok
9 Correct 1 ms 468 KB Ok
10 Correct 1 ms 468 KB Ok
11 Correct 1 ms 468 KB Ok
12 Correct 1 ms 568 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Ok
2 Correct 1 ms 560 KB Ok
3 Correct 1 ms 564 KB Ok
4 Correct 1 ms 468 KB Ok
5 Correct 1 ms 560 KB Ok
6 Correct 5 ms 724 KB Ok
7 Correct 23 ms 1468 KB Ok
8 Correct 11 ms 1020 KB Ok
9 Correct 27 ms 1756 KB Ok
10 Correct 15 ms 1200 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Ok
2 Correct 1 ms 468 KB Ok
3 Correct 1 ms 468 KB Ok
4 Correct 1 ms 468 KB Ok
5 Correct 1 ms 468 KB Ok
6 Correct 1 ms 468 KB Ok
7 Correct 1 ms 468 KB Ok
8 Correct 1 ms 468 KB Ok
9 Correct 1 ms 468 KB Ok
10 Correct 1 ms 468 KB Ok
11 Correct 1 ms 468 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 560 KB Ok
2 Correct 1 ms 564 KB Ok
3 Correct 1 ms 468 KB Ok
4 Correct 1 ms 560 KB Ok
5 Correct 1 ms 468 KB Ok
6 Correct 282 ms 14728 KB Ok
7 Correct 226 ms 16284 KB Ok
8 Correct 468 ms 18392 KB Ok
9 Correct 331 ms 18364 KB Ok
10 Correct 227 ms 10024 KB Ok
11 Correct 342 ms 19168 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Ok
2 Correct 1 ms 564 KB Ok
3 Correct 1 ms 568 KB Ok
4 Correct 1 ms 468 KB Ok
5 Correct 1 ms 468 KB Ok
6 Correct 1 ms 468 KB Ok
7 Correct 1 ms 560 KB Ok
8 Correct 1 ms 468 KB Ok
9 Correct 1 ms 468 KB Ok
10 Correct 1 ms 468 KB Ok
11 Correct 1 ms 468 KB Ok
12 Correct 1 ms 568 KB Ok
13 Correct 1 ms 468 KB Ok
14 Correct 1 ms 468 KB Ok
15 Correct 1 ms 468 KB Ok
16 Correct 1 ms 468 KB Ok
17 Correct 1 ms 468 KB Ok
18 Correct 1 ms 468 KB Ok
19 Correct 1 ms 468 KB Ok
20 Correct 1 ms 468 KB Ok
21 Correct 1 ms 468 KB Ok
22 Correct 1 ms 468 KB Ok
23 Correct 1 ms 468 KB Ok
24 Correct 5 ms 596 KB Ok
25 Correct 5 ms 560 KB Ok
26 Correct 5 ms 660 KB Ok
27 Correct 5 ms 596 KB Ok
28 Correct 4 ms 596 KB Ok
29 Correct 4 ms 664 KB Ok
30 Correct 4 ms 596 KB Ok
31 Correct 5 ms 564 KB Ok
32 Correct 5 ms 608 KB Ok
33 Correct 4 ms 596 KB Ok
34 Correct 9 ms 980 KB Ok
35 Correct 8 ms 952 KB Ok
36 Correct 9 ms 980 KB Ok
37 Correct 8 ms 980 KB Ok
38 Correct 9 ms 988 KB Ok
39 Correct 10 ms 948 KB Ok
40 Correct 9 ms 980 KB Ok
41 Correct 8 ms 972 KB Ok
42 Correct 9 ms 980 KB Ok
43 Correct 9 ms 980 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Ok
2 Correct 1 ms 564 KB Ok
3 Correct 1 ms 568 KB Ok
4 Correct 1 ms 468 KB Ok
5 Correct 1 ms 468 KB Ok
6 Correct 1 ms 468 KB Ok
7 Correct 1 ms 560 KB Ok
8 Correct 1 ms 468 KB Ok
9 Correct 1 ms 468 KB Ok
10 Correct 1 ms 468 KB Ok
11 Correct 1 ms 468 KB Ok
12 Correct 1 ms 568 KB Ok
13 Correct 1 ms 468 KB Ok
14 Correct 1 ms 560 KB Ok
15 Correct 1 ms 564 KB Ok
16 Correct 1 ms 468 KB Ok
17 Correct 1 ms 560 KB Ok
18 Correct 5 ms 724 KB Ok
19 Correct 23 ms 1468 KB Ok
20 Correct 11 ms 1020 KB Ok
21 Correct 27 ms 1756 KB Ok
22 Correct 15 ms 1200 KB Ok
23 Correct 1 ms 468 KB Ok
24 Correct 1 ms 468 KB Ok
25 Correct 1 ms 468 KB Ok
26 Correct 1 ms 468 KB Ok
27 Correct 1 ms 468 KB Ok
28 Correct 1 ms 468 KB Ok
29 Correct 1 ms 468 KB Ok
30 Correct 1 ms 468 KB Ok
31 Correct 1 ms 468 KB Ok
32 Correct 1 ms 468 KB Ok
33 Correct 1 ms 468 KB Ok
34 Correct 5 ms 596 KB Ok
35 Correct 5 ms 560 KB Ok
36 Correct 5 ms 660 KB Ok
37 Correct 5 ms 596 KB Ok
38 Correct 4 ms 596 KB Ok
39 Correct 4 ms 664 KB Ok
40 Correct 4 ms 596 KB Ok
41 Correct 5 ms 564 KB Ok
42 Correct 5 ms 608 KB Ok
43 Correct 4 ms 596 KB Ok
44 Correct 9 ms 980 KB Ok
45 Correct 8 ms 952 KB Ok
46 Correct 9 ms 980 KB Ok
47 Correct 8 ms 980 KB Ok
48 Correct 9 ms 988 KB Ok
49 Correct 10 ms 948 KB Ok
50 Correct 9 ms 980 KB Ok
51 Correct 8 ms 972 KB Ok
52 Correct 9 ms 980 KB Ok
53 Correct 9 ms 980 KB Ok
54 Correct 194 ms 3392 KB Ok
55 Correct 223 ms 3864 KB Ok
56 Correct 224 ms 3780 KB Ok
57 Correct 167 ms 2904 KB Ok
58 Correct 200 ms 3632 KB Ok
59 Correct 196 ms 3516 KB Ok
60 Correct 169 ms 3172 KB Ok
61 Correct 170 ms 3108 KB Ok
62 Correct 229 ms 4128 KB Ok
63 Correct 186 ms 3436 KB Ok
64 Correct 223 ms 3804 KB Ok
65 Correct 215 ms 3676 KB Ok
66 Correct 185 ms 3316 KB Ok
67 Correct 166 ms 3140 KB Ok
68 Correct 194 ms 3552 KB Ok
69 Correct 327 ms 13840 KB Ok
70 Correct 319 ms 14096 KB Ok
71 Correct 330 ms 13724 KB Ok
72 Correct 327 ms 13584 KB Ok
73 Correct 326 ms 14016 KB Ok
74 Correct 318 ms 13612 KB Ok
75 Correct 331 ms 13568 KB Ok
76 Correct 345 ms 13752 KB Ok
77 Correct 348 ms 13628 KB Ok
78 Correct 338 ms 13656 KB Ok
79 Correct 332 ms 14052 KB Ok
80 Correct 335 ms 13596 KB Ok
81 Correct 321 ms 14020 KB Ok
82 Correct 317 ms 13736 KB Ok
83 Correct 322 ms 13756 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Ok
2 Correct 1 ms 564 KB Ok
3 Correct 1 ms 568 KB Ok
4 Correct 1 ms 468 KB Ok
5 Correct 1 ms 468 KB Ok
6 Correct 1 ms 468 KB Ok
7 Correct 1 ms 560 KB Ok
8 Correct 1 ms 468 KB Ok
9 Correct 1 ms 468 KB Ok
10 Correct 1 ms 468 KB Ok
11 Correct 1 ms 468 KB Ok
12 Correct 1 ms 568 KB Ok
13 Correct 1 ms 468 KB Ok
14 Correct 1 ms 560 KB Ok
15 Correct 1 ms 564 KB Ok
16 Correct 1 ms 468 KB Ok
17 Correct 1 ms 560 KB Ok
18 Correct 5 ms 724 KB Ok
19 Correct 23 ms 1468 KB Ok
20 Correct 11 ms 1020 KB Ok
21 Correct 27 ms 1756 KB Ok
22 Correct 15 ms 1200 KB Ok
23 Correct 1 ms 468 KB Ok
24 Correct 1 ms 468 KB Ok
25 Correct 1 ms 468 KB Ok
26 Correct 1 ms 468 KB Ok
27 Correct 1 ms 468 KB Ok
28 Correct 1 ms 468 KB Ok
29 Correct 1 ms 468 KB Ok
30 Correct 1 ms 468 KB Ok
31 Correct 1 ms 468 KB Ok
32 Correct 1 ms 468 KB Ok
33 Correct 1 ms 468 KB Ok
34 Correct 1 ms 560 KB Ok
35 Correct 1 ms 564 KB Ok
36 Correct 1 ms 468 KB Ok
37 Correct 1 ms 560 KB Ok
38 Correct 1 ms 468 KB Ok
39 Correct 282 ms 14728 KB Ok
40 Correct 226 ms 16284 KB Ok
41 Correct 468 ms 18392 KB Ok
42 Correct 331 ms 18364 KB Ok
43 Correct 227 ms 10024 KB Ok
44 Correct 342 ms 19168 KB Ok
45 Correct 5 ms 596 KB Ok
46 Correct 5 ms 560 KB Ok
47 Correct 5 ms 660 KB Ok
48 Correct 5 ms 596 KB Ok
49 Correct 4 ms 596 KB Ok
50 Correct 4 ms 664 KB Ok
51 Correct 4 ms 596 KB Ok
52 Correct 5 ms 564 KB Ok
53 Correct 5 ms 608 KB Ok
54 Correct 4 ms 596 KB Ok
55 Correct 9 ms 980 KB Ok
56 Correct 8 ms 952 KB Ok
57 Correct 9 ms 980 KB Ok
58 Correct 8 ms 980 KB Ok
59 Correct 9 ms 988 KB Ok
60 Correct 10 ms 948 KB Ok
61 Correct 9 ms 980 KB Ok
62 Correct 8 ms 972 KB Ok
63 Correct 9 ms 980 KB Ok
64 Correct 9 ms 980 KB Ok
65 Correct 194 ms 3392 KB Ok
66 Correct 223 ms 3864 KB Ok
67 Correct 224 ms 3780 KB Ok
68 Correct 167 ms 2904 KB Ok
69 Correct 200 ms 3632 KB Ok
70 Correct 196 ms 3516 KB Ok
71 Correct 169 ms 3172 KB Ok
72 Correct 170 ms 3108 KB Ok
73 Correct 229 ms 4128 KB Ok
74 Correct 186 ms 3436 KB Ok
75 Correct 223 ms 3804 KB Ok
76 Correct 215 ms 3676 KB Ok
77 Correct 185 ms 3316 KB Ok
78 Correct 166 ms 3140 KB Ok
79 Correct 194 ms 3552 KB Ok
80 Correct 327 ms 13840 KB Ok
81 Correct 319 ms 14096 KB Ok
82 Correct 330 ms 13724 KB Ok
83 Correct 327 ms 13584 KB Ok
84 Correct 326 ms 14016 KB Ok
85 Correct 318 ms 13612 KB Ok
86 Correct 331 ms 13568 KB Ok
87 Correct 345 ms 13752 KB Ok
88 Correct 348 ms 13628 KB Ok
89 Correct 338 ms 13656 KB Ok
90 Correct 332 ms 14052 KB Ok
91 Correct 335 ms 13596 KB Ok
92 Correct 321 ms 14020 KB Ok
93 Correct 317 ms 13736 KB Ok
94 Correct 322 ms 13756 KB Ok
95 Correct 512 ms 8128 KB Ok
96 Correct 759 ms 12408 KB Ok
97 Correct 725 ms 10580 KB Ok
98 Correct 568 ms 8500 KB Ok
99 Correct 661 ms 9368 KB Ok
100 Correct 675 ms 10360 KB Ok
101 Correct 689 ms 9976 KB Ok
102 Correct 676 ms 10192 KB Ok
103 Correct 683 ms 10468 KB Ok
104 Correct 840 ms 11312 KB Ok
105 Correct 730 ms 11644 KB Ok
106 Correct 630 ms 9868 KB Ok
107 Correct 726 ms 10724 KB Ok
108 Correct 779 ms 11836 KB Ok
109 Correct 690 ms 11044 KB Ok
110 Correct 1450 ms 54680 KB Ok
111 Correct 1480 ms 56384 KB Ok
112 Correct 1447 ms 56760 KB Ok
113 Correct 1431 ms 55240 KB Ok
114 Correct 1441 ms 57192 KB Ok
115 Correct 1443 ms 56656 KB Ok
116 Correct 1470 ms 57184 KB Ok
117 Correct 1433 ms 55624 KB Ok
118 Correct 1417 ms 57416 KB Ok
119 Correct 1440 ms 55296 KB Ok
120 Correct 1434 ms 55964 KB Ok
121 Correct 1426 ms 55516 KB Ok
122 Correct 1402 ms 56016 KB Ok
123 Correct 1414 ms 56564 KB Ok
124 Correct 1458 ms 57024 KB Ok
125 Correct 1643 ms 39024 KB Ok