oj.uz

Submission #737110

# Submission time Handle Problem Language Result Execution time Memory
737110 2023-05-06T16:04:32 Z GrindMachine Nice sequence (IZhO18_sequence) C++17
100 / 100
 1677 ms 57164 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

upper bound for b.s?

find an upper bound for ans

ans < n+m

proof:
node u has incoming edges from u+n and u-m
u <= m: has incoming edge from u+n
u > m: has incoming edge from u-m

so for size >= n+m, every node has indeg >= 1
so no toposort exists

*/

const int MOD = 1e9 + 7;
const int N = 4e5 + 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 - 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:164:5: note: in expansion of macro 'rep'
  164 |     rep(i, sz(topo)) {
      |     ^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 424 KB Ok
3 Correct 1 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 1 ms 340 KB Ok
7 Correct 1 ms 340 KB Ok
8 Correct 1 ms 428 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 ms 340 KB Ok
11 Correct 1 ms 420 KB Ok
12 Correct 1 ms 340 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 420 KB Ok
3 Correct 1 ms 424 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 5 ms 596 KB Ok
7 Correct 25 ms 1388 KB Ok
8 Correct 10 ms 852 KB Ok
9 Correct 30 ms 1600 KB Ok
10 Correct 16 ms 980 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 420 KB Ok
2 Correct 1 ms 340 KB Ok
3 Correct 1 ms 468 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 416 KB Ok
6 Correct 299 ms 14580 KB Ok
7 Correct 227 ms 16248 KB Ok
8 Correct 459 ms 18212 KB Ok
9 Correct 323 ms 18220 KB Ok
10 Correct 197 ms 9824 KB Ok
11 Correct 337 ms 19064 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 424 KB Ok
3 Correct 1 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 1 ms 340 KB Ok
7 Correct 1 ms 340 KB Ok
8 Correct 1 ms 428 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 ms 340 KB Ok
11 Correct 1 ms 420 KB Ok
12 Correct 1 ms 340 KB Ok
13 Correct 1 ms 340 KB Ok
14 Correct 1 ms 340 KB Ok
15 Correct 1 ms 340 KB Ok
16 Correct 1 ms 340 KB Ok
17 Correct 1 ms 340 KB Ok
18 Correct 1 ms 340 KB Ok
19 Correct 1 ms 340 KB Ok
20 Correct 1 ms 340 KB Ok
21 Correct 1 ms 340 KB Ok
22 Correct 1 ms 340 KB Ok
23 Correct 1 ms 340 KB Ok
24 Correct 5 ms 464 KB Ok
25 Correct 5 ms 468 KB Ok
26 Correct 4 ms 468 KB Ok
27 Correct 4 ms 480 KB Ok
28 Correct 4 ms 420 KB Ok
29 Correct 4 ms 468 KB Ok
30 Correct 3 ms 596 KB Ok
31 Correct 4 ms 468 KB Ok
32 Correct 4 ms 468 KB Ok
33 Correct 4 ms 468 KB Ok
34 Correct 9 ms 744 KB Ok
35 Correct 9 ms 756 KB Ok
36 Correct 8 ms 840 KB Ok
37 Correct 9 ms 852 KB Ok
38 Correct 8 ms 852 KB Ok
39 Correct 9 ms 724 KB Ok
40 Correct 9 ms 852 KB Ok
41 Correct 9 ms 828 KB Ok
42 Correct 8 ms 852 KB Ok
43 Correct 9 ms 844 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 424 KB Ok
3 Correct 1 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 1 ms 340 KB Ok
7 Correct 1 ms 340 KB Ok
8 Correct 1 ms 428 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 ms 340 KB Ok
11 Correct 1 ms 420 KB Ok
12 Correct 1 ms 340 KB Ok
13 Correct 1 ms 340 KB Ok
14 Correct 1 ms 420 KB Ok
15 Correct 1 ms 424 KB Ok
16 Correct 1 ms 340 KB Ok
17 Correct 1 ms 340 KB Ok
18 Correct 5 ms 596 KB Ok
19 Correct 25 ms 1388 KB Ok
20 Correct 10 ms 852 KB Ok
21 Correct 30 ms 1600 KB Ok
22 Correct 16 ms 980 KB Ok
23 Correct 1 ms 340 KB Ok
24 Correct 1 ms 340 KB Ok
25 Correct 1 ms 340 KB Ok
26 Correct 1 ms 340 KB Ok
27 Correct 1 ms 340 KB Ok
28 Correct 1 ms 340 KB Ok
29 Correct 1 ms 340 KB Ok
30 Correct 1 ms 340 KB Ok
31 Correct 1 ms 340 KB Ok
32 Correct 1 ms 340 KB Ok
33 Correct 1 ms 340 KB Ok
34 Correct 5 ms 464 KB Ok
35 Correct 5 ms 468 KB Ok
36 Correct 4 ms 468 KB Ok
37 Correct 4 ms 480 KB Ok
38 Correct 4 ms 420 KB Ok
39 Correct 4 ms 468 KB Ok
40 Correct 3 ms 596 KB Ok
41 Correct 4 ms 468 KB Ok
42 Correct 4 ms 468 KB Ok
43 Correct 4 ms 468 KB Ok
44 Correct 9 ms 744 KB Ok
45 Correct 9 ms 756 KB Ok
46 Correct 8 ms 840 KB Ok
47 Correct 9 ms 852 KB Ok
48 Correct 8 ms 852 KB Ok
49 Correct 9 ms 724 KB Ok
50 Correct 9 ms 852 KB Ok
51 Correct 9 ms 828 KB Ok
52 Correct 8 ms 852 KB Ok
53 Correct 9 ms 844 KB Ok
54 Correct 176 ms 3276 KB Ok
55 Correct 174 ms 3672 KB Ok
56 Correct 172 ms 3548 KB Ok
57 Correct 139 ms 2856 KB Ok
58 Correct 180 ms 3520 KB Ok
59 Correct 152 ms 3408 KB Ok
60 Correct 147 ms 2988 KB Ok
61 Correct 132 ms 2960 KB Ok
62 Correct 193 ms 3936 KB Ok
63 Correct 151 ms 3156 KB Ok
64 Correct 186 ms 3684 KB Ok
65 Correct 173 ms 3476 KB Ok
66 Correct 155 ms 3100 KB Ok
67 Correct 168 ms 2988 KB Ok
68 Correct 157 ms 3416 KB Ok
69 Correct 331 ms 13624 KB Ok
70 Correct 331 ms 13884 KB Ok
71 Correct 306 ms 13608 KB Ok
72 Correct 341 ms 13420 KB Ok
73 Correct 333 ms 13744 KB Ok
74 Correct 298 ms 13496 KB Ok
75 Correct 321 ms 13640 KB Ok
76 Correct 367 ms 13704 KB Ok
77 Correct 298 ms 13568 KB Ok
78 Correct 357 ms 13376 KB Ok
79 Correct 325 ms 13948 KB Ok
80 Correct 302 ms 13428 KB Ok
81 Correct 314 ms 13812 KB Ok
82 Correct 355 ms 13616 KB Ok
83 Correct 315 ms 13624 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 424 KB Ok
3 Correct 1 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 1 ms 340 KB Ok
7 Correct 1 ms 340 KB Ok
8 Correct 1 ms 428 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 ms 340 KB Ok
11 Correct 1 ms 420 KB Ok
12 Correct 1 ms 340 KB Ok
13 Correct 1 ms 340 KB Ok
14 Correct 1 ms 420 KB Ok
15 Correct 1 ms 424 KB Ok
16 Correct 1 ms 340 KB Ok
17 Correct 1 ms 340 KB Ok
18 Correct 5 ms 596 KB Ok
19 Correct 25 ms 1388 KB Ok
20 Correct 10 ms 852 KB Ok
21 Correct 30 ms 1600 KB Ok
22 Correct 16 ms 980 KB Ok
23 Correct 1 ms 340 KB Ok
24 Correct 1 ms 340 KB Ok
25 Correct 1 ms 340 KB Ok
26 Correct 1 ms 340 KB Ok
27 Correct 1 ms 340 KB Ok
28 Correct 1 ms 340 KB Ok
29 Correct 1 ms 340 KB Ok
30 Correct 1 ms 340 KB Ok
31 Correct 1 ms 340 KB Ok
32 Correct 1 ms 340 KB Ok
33 Correct 1 ms 340 KB Ok
34 Correct 1 ms 420 KB Ok
35 Correct 1 ms 340 KB Ok
36 Correct 1 ms 468 KB Ok
37 Correct 1 ms 340 KB Ok
38 Correct 1 ms 416 KB Ok
39 Correct 299 ms 14580 KB Ok
40 Correct 227 ms 16248 KB Ok
41 Correct 459 ms 18212 KB Ok
42 Correct 323 ms 18220 KB Ok
43 Correct 197 ms 9824 KB Ok
44 Correct 337 ms 19064 KB Ok
45 Correct 5 ms 464 KB Ok
46 Correct 5 ms 468 KB Ok
47 Correct 4 ms 468 KB Ok
48 Correct 4 ms 480 KB Ok
49 Correct 4 ms 420 KB Ok
50 Correct 4 ms 468 KB Ok
51 Correct 3 ms 596 KB Ok
52 Correct 4 ms 468 KB Ok
53 Correct 4 ms 468 KB Ok
54 Correct 4 ms 468 KB Ok
55 Correct 9 ms 744 KB Ok
56 Correct 9 ms 756 KB Ok
57 Correct 8 ms 840 KB Ok
58 Correct 9 ms 852 KB Ok
59 Correct 8 ms 852 KB Ok
60 Correct 9 ms 724 KB Ok
61 Correct 9 ms 852 KB Ok
62 Correct 9 ms 828 KB Ok
63 Correct 8 ms 852 KB Ok
64 Correct 9 ms 844 KB Ok
65 Correct 176 ms 3276 KB Ok
66 Correct 174 ms 3672 KB Ok
67 Correct 172 ms 3548 KB Ok
68 Correct 139 ms 2856 KB Ok
69 Correct 180 ms 3520 KB Ok
70 Correct 152 ms 3408 KB Ok
71 Correct 147 ms 2988 KB Ok
72 Correct 132 ms 2960 KB Ok
73 Correct 193 ms 3936 KB Ok
74 Correct 151 ms 3156 KB Ok
75 Correct 186 ms 3684 KB Ok
76 Correct 173 ms 3476 KB Ok
77 Correct 155 ms 3100 KB Ok
78 Correct 168 ms 2988 KB Ok
79 Correct 157 ms 3416 KB Ok
80 Correct 331 ms 13624 KB Ok
81 Correct 331 ms 13884 KB Ok
82 Correct 306 ms 13608 KB Ok
83 Correct 341 ms 13420 KB Ok
84 Correct 333 ms 13744 KB Ok
85 Correct 298 ms 13496 KB Ok
86 Correct 321 ms 13640 KB Ok
87 Correct 367 ms 13704 KB Ok
88 Correct 298 ms 13568 KB Ok
89 Correct 357 ms 13376 KB Ok
90 Correct 325 ms 13948 KB Ok
91 Correct 302 ms 13428 KB Ok
92 Correct 314 ms 13812 KB Ok
93 Correct 355 ms 13616 KB Ok
94 Correct 315 ms 13624 KB Ok
95 Correct 441 ms 7956 KB Ok
96 Correct 618 ms 12420 KB Ok
97 Correct 534 ms 10308 KB Ok
98 Correct 468 ms 8324 KB Ok
99 Correct 493 ms 9176 KB Ok
100 Correct 573 ms 10188 KB Ok
101 Correct 548 ms 9780 KB Ok
102 Correct 588 ms 10012 KB Ok
103 Correct 535 ms 10316 KB Ok
104 Correct 667 ms 11172 KB Ok
105 Correct 606 ms 12564 KB Ok
106 Correct 533 ms 9680 KB Ok
107 Correct 581 ms 10576 KB Ok
108 Correct 648 ms 11644 KB Ok
109 Correct 573 ms 10784 KB Ok
110 Correct 1426 ms 54400 KB Ok
111 Correct 1502 ms 56440 KB Ok
112 Correct 1419 ms 56624 KB Ok
113 Correct 1472 ms 55092 KB Ok
114 Correct 1446 ms 57036 KB Ok
115 Correct 1484 ms 56376 KB Ok
116 Correct 1443 ms 57056 KB Ok
117 Correct 1446 ms 55560 KB Ok
118 Correct 1408 ms 57164 KB Ok
119 Correct 1507 ms 55204 KB Ok
120 Correct 1425 ms 55832 KB Ok
121 Correct 1387 ms 55392 KB Ok
122 Correct 1415 ms 55876 KB Ok
123 Correct 1475 ms 56388 KB Ok
124 Correct 1433 ms 56948 KB Ok
125 Correct 1677 ms 38560 KB Ok