oj.uz

Submission #737074

# Submission time Handle Problem Language Result Execution time Memory
737074 2023-05-06T14:29:36 Z GrindMachine Nice sequence (IZhO18_sequence) C++17
100 / 100
 1692 ms 57248 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);
            if (cyc) return false;
        }

        reverse(all(topo));
        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:150:5: note: in expansion of macro 'rep'
  150 |     rep(i, sz(topo)) {
      |     ^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 564 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 2 ms 468 KB Ok
6 Correct 1 ms 564 KB Ok
7 Correct 1 ms 468 KB Ok
8 Correct 1 ms 568 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 468 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 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 6 ms 724 KB Ok
7 Correct 22 ms 1516 KB Ok
8 Correct 11 ms 980 KB Ok
9 Correct 27 ms 1748 KB Ok
10 Correct 15 ms 1212 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 564 KB Ok
2 Correct 1 ms 468 KB Ok
3 Correct 1 ms 564 KB Ok
4 Correct 1 ms 568 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 568 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 468 KB Ok
6 Correct 298 ms 14684 KB Ok
7 Correct 248 ms 16400 KB Ok
8 Correct 477 ms 18480 KB Ok
9 Correct 341 ms 18360 KB Ok
10 Correct 211 ms 10012 KB Ok
11 Correct 368 ms 19288 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 564 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 2 ms 468 KB Ok
6 Correct 1 ms 564 KB Ok
7 Correct 1 ms 468 KB Ok
8 Correct 1 ms 568 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 468 KB Ok
13 Correct 1 ms 564 KB Ok
14 Correct 1 ms 468 KB Ok
15 Correct 1 ms 564 KB Ok
16 Correct 1 ms 568 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 4 ms 596 KB Ok
26 Correct 5 ms 596 KB Ok
27 Correct 5 ms 596 KB Ok
28 Correct 4 ms 596 KB Ok
29 Correct 3 ms 596 KB Ok
30 Correct 3 ms 596 KB Ok
31 Correct 4 ms 596 KB Ok
32 Correct 4 ms 596 KB Ok
33 Correct 4 ms 596 KB Ok
34 Correct 9 ms 948 KB Ok
35 Correct 8 ms 980 KB Ok
36 Correct 11 ms 980 KB Ok
37 Correct 10 ms 944 KB Ok
38 Correct 8 ms 980 KB Ok
39 Correct 8 ms 980 KB Ok
40 Correct 9 ms 948 KB Ok
41 Correct 8 ms 980 KB Ok
42 Correct 8 ms 944 KB Ok
43 Correct 10 ms 956 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 564 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 2 ms 468 KB Ok
6 Correct 1 ms 564 KB Ok
7 Correct 1 ms 468 KB Ok
8 Correct 1 ms 568 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 468 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 6 ms 724 KB Ok
19 Correct 22 ms 1516 KB Ok
20 Correct 11 ms 980 KB Ok
21 Correct 27 ms 1748 KB Ok
22 Correct 15 ms 1212 KB Ok
23 Correct 1 ms 564 KB Ok
24 Correct 1 ms 468 KB Ok
25 Correct 1 ms 564 KB Ok
26 Correct 1 ms 568 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 4 ms 596 KB Ok
36 Correct 5 ms 596 KB Ok
37 Correct 5 ms 596 KB Ok
38 Correct 4 ms 596 KB Ok
39 Correct 3 ms 596 KB Ok
40 Correct 3 ms 596 KB Ok
41 Correct 4 ms 596 KB Ok
42 Correct 4 ms 596 KB Ok
43 Correct 4 ms 596 KB Ok
44 Correct 9 ms 948 KB Ok
45 Correct 8 ms 980 KB Ok
46 Correct 11 ms 980 KB Ok
47 Correct 10 ms 944 KB Ok
48 Correct 8 ms 980 KB Ok
49 Correct 8 ms 980 KB Ok
50 Correct 9 ms 948 KB Ok
51 Correct 8 ms 980 KB Ok
52 Correct 8 ms 944 KB Ok
53 Correct 10 ms 956 KB Ok
54 Correct 167 ms 3424 KB Ok
55 Correct 175 ms 3848 KB Ok
56 Correct 180 ms 3656 KB Ok
57 Correct 147 ms 2924 KB Ok
58 Correct 176 ms 3652 KB Ok
59 Correct 150 ms 3496 KB Ok
60 Correct 148 ms 3180 KB Ok
61 Correct 128 ms 3020 KB Ok
62 Correct 185 ms 4032 KB Ok
63 Correct 155 ms 3304 KB Ok
64 Correct 198 ms 3836 KB Ok
65 Correct 171 ms 3716 KB Ok
66 Correct 169 ms 3288 KB Ok
67 Correct 156 ms 3136 KB Ok
68 Correct 168 ms 3560 KB Ok
69 Correct 346 ms 13788 KB Ok
70 Correct 364 ms 14120 KB Ok
71 Correct 342 ms 13768 KB Ok
72 Correct 336 ms 13536 KB Ok
73 Correct 316 ms 13880 KB Ok
74 Correct 313 ms 13636 KB Ok
75 Correct 298 ms 13768 KB Ok
76 Correct 367 ms 13760 KB Ok
77 Correct 325 ms 13548 KB Ok
78 Correct 329 ms 13584 KB Ok
79 Correct 309 ms 14020 KB Ok
80 Correct 323 ms 13604 KB Ok
81 Correct 338 ms 14016 KB Ok
82 Correct 324 ms 13756 KB Ok
83 Correct 345 ms 13768 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 564 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 2 ms 468 KB Ok
6 Correct 1 ms 564 KB Ok
7 Correct 1 ms 468 KB Ok
8 Correct 1 ms 568 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 468 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 6 ms 724 KB Ok
19 Correct 22 ms 1516 KB Ok
20 Correct 11 ms 980 KB Ok
21 Correct 27 ms 1748 KB Ok
22 Correct 15 ms 1212 KB Ok
23 Correct 1 ms 564 KB Ok
24 Correct 1 ms 468 KB Ok
25 Correct 1 ms 564 KB Ok
26 Correct 1 ms 568 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 568 KB Ok
35 Correct 1 ms 560 KB Ok
36 Correct 1 ms 564 KB Ok
37 Correct 1 ms 468 KB Ok
38 Correct 1 ms 468 KB Ok
39 Correct 298 ms 14684 KB Ok
40 Correct 248 ms 16400 KB Ok
41 Correct 477 ms 18480 KB Ok
42 Correct 341 ms 18360 KB Ok
43 Correct 211 ms 10012 KB Ok
44 Correct 368 ms 19288 KB Ok
45 Correct 5 ms 596 KB Ok
46 Correct 4 ms 596 KB Ok
47 Correct 5 ms 596 KB Ok
48 Correct 5 ms 596 KB Ok
49 Correct 4 ms 596 KB Ok
50 Correct 3 ms 596 KB Ok
51 Correct 3 ms 596 KB Ok
52 Correct 4 ms 596 KB Ok
53 Correct 4 ms 596 KB Ok
54 Correct 4 ms 596 KB Ok
55 Correct 9 ms 948 KB Ok
56 Correct 8 ms 980 KB Ok
57 Correct 11 ms 980 KB Ok
58 Correct 10 ms 944 KB Ok
59 Correct 8 ms 980 KB Ok
60 Correct 8 ms 980 KB Ok
61 Correct 9 ms 948 KB Ok
62 Correct 8 ms 980 KB Ok
63 Correct 8 ms 944 KB Ok
64 Correct 10 ms 956 KB Ok
65 Correct 167 ms 3424 KB Ok
66 Correct 175 ms 3848 KB Ok
67 Correct 180 ms 3656 KB Ok
68 Correct 147 ms 2924 KB Ok
69 Correct 176 ms 3652 KB Ok
70 Correct 150 ms 3496 KB Ok
71 Correct 148 ms 3180 KB Ok
72 Correct 128 ms 3020 KB Ok
73 Correct 185 ms 4032 KB Ok
74 Correct 155 ms 3304 KB Ok
75 Correct 198 ms 3836 KB Ok
76 Correct 171 ms 3716 KB Ok
77 Correct 169 ms 3288 KB Ok
78 Correct 156 ms 3136 KB Ok
79 Correct 168 ms 3560 KB Ok
80 Correct 346 ms 13788 KB Ok
81 Correct 364 ms 14120 KB Ok
82 Correct 342 ms 13768 KB Ok
83 Correct 336 ms 13536 KB Ok
84 Correct 316 ms 13880 KB Ok
85 Correct 313 ms 13636 KB Ok
86 Correct 298 ms 13768 KB Ok
87 Correct 367 ms 13760 KB Ok
88 Correct 325 ms 13548 KB Ok
89 Correct 329 ms 13584 KB Ok
90 Correct 309 ms 14020 KB Ok
91 Correct 323 ms 13604 KB Ok
92 Correct 338 ms 14016 KB Ok
93 Correct 324 ms 13756 KB Ok
94 Correct 345 ms 13768 KB Ok
95 Correct 414 ms 8092 KB Ok
96 Correct 589 ms 12492 KB Ok
97 Correct 553 ms 10456 KB Ok
98 Correct 449 ms 8528 KB Ok
99 Correct 514 ms 9320 KB Ok
100 Correct 517 ms 10388 KB Ok
101 Correct 578 ms 9924 KB Ok
102 Correct 557 ms 10088 KB Ok
103 Correct 532 ms 10404 KB Ok
104 Correct 653 ms 11320 KB Ok
105 Correct 579 ms 11560 KB Ok
106 Correct 547 ms 9940 KB Ok
107 Correct 647 ms 10768 KB Ok
108 Correct 605 ms 11772 KB Ok
109 Correct 538 ms 10984 KB Ok
110 Correct 1394 ms 54468 KB Ok
111 Correct 1560 ms 56432 KB Ok
112 Correct 1460 ms 56824 KB Ok
113 Correct 1472 ms 55212 KB Ok
114 Correct 1502 ms 57228 KB Ok
115 Correct 1535 ms 56720 KB Ok
116 Correct 1469 ms 57248 KB Ok
117 Correct 1462 ms 55952 KB Ok
118 Correct 1417 ms 57168 KB Ok
119 Correct 1530 ms 55248 KB Ok
120 Correct 1507 ms 55992 KB Ok
121 Correct 1456 ms 55548 KB Ok
122 Correct 1432 ms 56036 KB Ok
123 Correct 1486 ms 56512 KB Ok
124 Correct 1426 ms 57072 KB Ok
125 Correct 1692 ms 38756 KB Ok