oj.uz

Submission #737067

# Submission time Handle Problem Language Result Execution time Memory
737067 2023-05-06T14:23:39 Z GrindMachine Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 75984 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;
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 - 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:152:5: note: in expansion of macro 'rep'
  152 |     rep(i, sz(topo)) {
      |     ^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 57460 KB Ok
2 Correct 253 ms 57416 KB Ok
3 Correct 184 ms 28436 KB Ok
4 Correct 176 ms 30528 KB Ok
5 Correct 189 ms 28344 KB Ok
6 Correct 176 ms 33924 KB Ok
7 Correct 172 ms 27616 KB Ok
8 Correct 179 ms 34000 KB Ok
9 Correct 192 ms 28232 KB Ok
10 Correct 182 ms 41756 KB Ok
11 Correct 171 ms 27696 KB Ok
12 Correct 191 ms 27100 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 57400 KB Ok
2 Correct 280 ms 57340 KB Ok
3 Correct 260 ms 57408 KB Ok
4 Correct 245 ms 57376 KB Ok
5 Correct 271 ms 57412 KB Ok
6 Correct 256 ms 57480 KB Ok
7 Correct 263 ms 57588 KB Ok
8 Correct 288 ms 57688 KB Ok
9 Correct 286 ms 57872 KB Ok
10 Correct 261 ms 57480 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 57508 KB Ok
2 Correct 263 ms 57572 KB Ok
3 Correct 240 ms 57404 KB Ok
4 Correct 246 ms 57632 KB Ok
5 Correct 230 ms 57516 KB Ok
6 Correct 248 ms 57364 KB Ok
7 Correct 216 ms 57552 KB Ok
8 Correct 252 ms 57524 KB Ok
9 Correct 234 ms 57404 KB Ok
10 Correct 229 ms 57368 KB Ok
11 Correct 236 ms 57336 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 57440 KB Ok
2 Correct 259 ms 57544 KB Ok
3 Correct 234 ms 57468 KB Ok
4 Correct 254 ms 57416 KB Ok
5 Correct 243 ms 57532 KB Ok
6 Correct 533 ms 61556 KB Ok
7 Correct 514 ms 60056 KB Ok
8 Correct 782 ms 62792 KB Ok
9 Correct 604 ms 63324 KB Ok
10 Correct 449 ms 59832 KB Ok
11 Correct 583 ms 62664 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 57460 KB Ok
2 Correct 253 ms 57416 KB Ok
3 Correct 184 ms 28436 KB Ok
4 Correct 176 ms 30528 KB Ok
5 Correct 189 ms 28344 KB Ok
6 Correct 176 ms 33924 KB Ok
7 Correct 172 ms 27616 KB Ok
8 Correct 179 ms 34000 KB Ok
9 Correct 192 ms 28232 KB Ok
10 Correct 182 ms 41756 KB Ok
11 Correct 171 ms 27696 KB Ok
12 Correct 191 ms 27100 KB Ok
13 Correct 95 ms 57508 KB Ok
14 Correct 263 ms 57572 KB Ok
15 Correct 240 ms 57404 KB Ok
16 Correct 246 ms 57632 KB Ok
17 Correct 230 ms 57516 KB Ok
18 Correct 248 ms 57364 KB Ok
19 Correct 216 ms 57552 KB Ok
20 Correct 252 ms 57524 KB Ok
21 Correct 234 ms 57404 KB Ok
22 Correct 229 ms 57368 KB Ok
23 Correct 236 ms 57336 KB Ok
24 Correct 195 ms 26292 KB Ok
25 Correct 181 ms 26744 KB Ok
26 Correct 190 ms 28432 KB Ok
27 Correct 194 ms 28492 KB Ok
28 Correct 191 ms 26740 KB Ok
29 Correct 179 ms 36476 KB Ok
30 Correct 184 ms 27600 KB Ok
31 Correct 208 ms 26736 KB Ok
32 Correct 170 ms 26448 KB Ok
33 Correct 173 ms 27800 KB Ok
34 Correct 237 ms 57464 KB Ok
35 Correct 263 ms 57572 KB Ok
36 Correct 252 ms 57416 KB Ok
37 Correct 244 ms 57588 KB Ok
38 Correct 257 ms 57452 KB Ok
39 Correct 219 ms 57560 KB Ok
40 Correct 248 ms 57500 KB Ok
41 Correct 255 ms 57488 KB Ok
42 Correct 232 ms 57464 KB Ok
43 Correct 325 ms 57576 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 57460 KB Ok
2 Correct 253 ms 57416 KB Ok
3 Correct 184 ms 28436 KB Ok
4 Correct 176 ms 30528 KB Ok
5 Correct 189 ms 28344 KB Ok
6 Correct 176 ms 33924 KB Ok
7 Correct 172 ms 27616 KB Ok
8 Correct 179 ms 34000 KB Ok
9 Correct 192 ms 28232 KB Ok
10 Correct 182 ms 41756 KB Ok
11 Correct 171 ms 27696 KB Ok
12 Correct 191 ms 27100 KB Ok
13 Correct 252 ms 57400 KB Ok
14 Correct 280 ms 57340 KB Ok
15 Correct 260 ms 57408 KB Ok
16 Correct 245 ms 57376 KB Ok
17 Correct 271 ms 57412 KB Ok
18 Correct 256 ms 57480 KB Ok
19 Correct 263 ms 57588 KB Ok
20 Correct 288 ms 57688 KB Ok
21 Correct 286 ms 57872 KB Ok
22 Correct 261 ms 57480 KB Ok
23 Correct 95 ms 57508 KB Ok
24 Correct 263 ms 57572 KB Ok
25 Correct 240 ms 57404 KB Ok
26 Correct 246 ms 57632 KB Ok
27 Correct 230 ms 57516 KB Ok
28 Correct 248 ms 57364 KB Ok
29 Correct 216 ms 57552 KB Ok
30 Correct 252 ms 57524 KB Ok
31 Correct 234 ms 57404 KB Ok
32 Correct 229 ms 57368 KB Ok
33 Correct 236 ms 57336 KB Ok
34 Correct 195 ms 26292 KB Ok
35 Correct 181 ms 26744 KB Ok
36 Correct 190 ms 28432 KB Ok
37 Correct 194 ms 28492 KB Ok
38 Correct 191 ms 26740 KB Ok
39 Correct 179 ms 36476 KB Ok
40 Correct 184 ms 27600 KB Ok
41 Correct 208 ms 26736 KB Ok
42 Correct 170 ms 26448 KB Ok
43 Correct 173 ms 27800 KB Ok
44 Correct 237 ms 57464 KB Ok
45 Correct 263 ms 57572 KB Ok
46 Correct 252 ms 57416 KB Ok
47 Correct 244 ms 57588 KB Ok
48 Correct 257 ms 57452 KB Ok
49 Correct 219 ms 57560 KB Ok
50 Correct 248 ms 57500 KB Ok
51 Correct 255 ms 57488 KB Ok
52 Correct 232 ms 57464 KB Ok
53 Correct 325 ms 57576 KB Ok
54 Correct 362 ms 28584 KB Ok
55 Correct 389 ms 28936 KB Ok
56 Correct 385 ms 28876 KB Ok
57 Correct 339 ms 28080 KB Ok
58 Correct 375 ms 28796 KB Ok
59 Correct 366 ms 28596 KB Ok
60 Correct 375 ms 28352 KB Ok
61 Correct 369 ms 28180 KB Ok
62 Correct 416 ms 29048 KB Ok
63 Correct 341 ms 28628 KB Ok
64 Correct 390 ms 28956 KB Ok
65 Correct 390 ms 28728 KB Ok
66 Correct 355 ms 28480 KB Ok
67 Correct 329 ms 28208 KB Ok
68 Correct 390 ms 28908 KB Ok
69 Correct 591 ms 63768 KB Ok
70 Correct 593 ms 64132 KB Ok
71 Correct 559 ms 63832 KB Ok
72 Correct 584 ms 63764 KB Ok
73 Correct 575 ms 64012 KB Ok
74 Correct 541 ms 63692 KB Ok
75 Correct 547 ms 63712 KB Ok
76 Correct 615 ms 63860 KB Ok
77 Correct 543 ms 63628 KB Ok
78 Correct 619 ms 63780 KB Ok
79 Correct 563 ms 64068 KB Ok
80 Correct 551 ms 63620 KB Ok
81 Correct 618 ms 64056 KB Ok
82 Correct 673 ms 63772 KB Ok
83 Correct 597 ms 63956 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 57460 KB Ok
2 Correct 253 ms 57416 KB Ok
3 Correct 184 ms 28436 KB Ok
4 Correct 176 ms 30528 KB Ok
5 Correct 189 ms 28344 KB Ok
6 Correct 176 ms 33924 KB Ok
7 Correct 172 ms 27616 KB Ok
8 Correct 179 ms 34000 KB Ok
9 Correct 192 ms 28232 KB Ok
10 Correct 182 ms 41756 KB Ok
11 Correct 171 ms 27696 KB Ok
12 Correct 191 ms 27100 KB Ok
13 Correct 252 ms 57400 KB Ok
14 Correct 280 ms 57340 KB Ok
15 Correct 260 ms 57408 KB Ok
16 Correct 245 ms 57376 KB Ok
17 Correct 271 ms 57412 KB Ok
18 Correct 256 ms 57480 KB Ok
19 Correct 263 ms 57588 KB Ok
20 Correct 288 ms 57688 KB Ok
21 Correct 286 ms 57872 KB Ok
22 Correct 261 ms 57480 KB Ok
23 Correct 95 ms 57508 KB Ok
24 Correct 263 ms 57572 KB Ok
25 Correct 240 ms 57404 KB Ok
26 Correct 246 ms 57632 KB Ok
27 Correct 230 ms 57516 KB Ok
28 Correct 248 ms 57364 KB Ok
29 Correct 216 ms 57552 KB Ok
30 Correct 252 ms 57524 KB Ok
31 Correct 234 ms 57404 KB Ok
32 Correct 229 ms 57368 KB Ok
33 Correct 236 ms 57336 KB Ok
34 Correct 249 ms 57440 KB Ok
35 Correct 259 ms 57544 KB Ok
36 Correct 234 ms 57468 KB Ok
37 Correct 254 ms 57416 KB Ok
38 Correct 243 ms 57532 KB Ok
39 Correct 533 ms 61556 KB Ok
40 Correct 514 ms 60056 KB Ok
41 Correct 782 ms 62792 KB Ok
42 Correct 604 ms 63324 KB Ok
43 Correct 449 ms 59832 KB Ok
44 Correct 583 ms 62664 KB Ok
45 Correct 195 ms 26292 KB Ok
46 Correct 181 ms 26744 KB Ok
47 Correct 190 ms 28432 KB Ok
48 Correct 194 ms 28492 KB Ok
49 Correct 191 ms 26740 KB Ok
50 Correct 179 ms 36476 KB Ok
51 Correct 184 ms 27600 KB Ok
52 Correct 208 ms 26736 KB Ok
53 Correct 170 ms 26448 KB Ok
54 Correct 173 ms 27800 KB Ok
55 Correct 237 ms 57464 KB Ok
56 Correct 263 ms 57572 KB Ok
57 Correct 252 ms 57416 KB Ok
58 Correct 244 ms 57588 KB Ok
59 Correct 257 ms 57452 KB Ok
60 Correct 219 ms 57560 KB Ok
61 Correct 248 ms 57500 KB Ok
62 Correct 255 ms 57488 KB Ok
63 Correct 232 ms 57464 KB Ok
64 Correct 325 ms 57576 KB Ok
65 Correct 362 ms 28584 KB Ok
66 Correct 389 ms 28936 KB Ok
67 Correct 385 ms 28876 KB Ok
68 Correct 339 ms 28080 KB Ok
69 Correct 375 ms 28796 KB Ok
70 Correct 366 ms 28596 KB Ok
71 Correct 375 ms 28352 KB Ok
72 Correct 369 ms 28180 KB Ok
73 Correct 416 ms 29048 KB Ok
74 Correct 341 ms 28628 KB Ok
75 Correct 390 ms 28956 KB Ok
76 Correct 390 ms 28728 KB Ok
77 Correct 355 ms 28480 KB Ok
78 Correct 329 ms 28208 KB Ok
79 Correct 390 ms 28908 KB Ok
80 Correct 591 ms 63768 KB Ok
81 Correct 593 ms 64132 KB Ok
82 Correct 559 ms 63832 KB Ok
83 Correct 584 ms 63764 KB Ok
84 Correct 575 ms 64012 KB Ok
85 Correct 541 ms 63692 KB Ok
86 Correct 547 ms 63712 KB Ok
87 Correct 615 ms 63860 KB Ok
88 Correct 543 ms 63628 KB Ok
89 Correct 619 ms 63780 KB Ok
90 Correct 563 ms 64068 KB Ok
91 Correct 551 ms 63620 KB Ok
92 Correct 618 ms 64056 KB Ok
93 Correct 673 ms 63772 KB Ok
94 Correct 597 ms 63956 KB Ok
95 Correct 683 ms 32916 KB Ok
96 Correct 990 ms 36428 KB Ok
97 Correct 961 ms 34828 KB Ok
98 Correct 766 ms 32740 KB Ok
99 Correct 872 ms 33664 KB Ok
100 Correct 917 ms 34740 KB Ok
101 Correct 953 ms 34032 KB Ok
102 Correct 893 ms 34404 KB Ok
103 Correct 879 ms 34688 KB Ok
104 Correct 1041 ms 35432 KB Ok
105 Correct 915 ms 35520 KB Ok
106 Correct 827 ms 33904 KB Ok
107 Correct 896 ms 34920 KB Ok
108 Correct 1077 ms 35948 KB Ok
109 Correct 908 ms 34892 KB Ok
110 Execution timed out 2080 ms 75984 KB Time limit exceeded
111 Halted 0 ms 0 KB -