oj.uz

Submission #737068

# Submission time Handle Problem Language Result Execution time Memory
737068 2023-05-06T14:24:30 Z GrindMachine Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 57736 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 - 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: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 266 ms 34024 KB Ok
2 Correct 276 ms 34000 KB Ok
3 Correct 202 ms 5004 KB Ok
4 Correct 165 ms 7104 KB Ok
5 Correct 171 ms 4888 KB Ok
6 Correct 201 ms 10440 KB Ok
7 Correct 161 ms 4144 KB Ok
8 Correct 177 ms 10540 KB Ok
9 Correct 178 ms 4728 KB Ok
10 Correct 192 ms 18284 KB Ok
11 Correct 193 ms 4108 KB Ok
12 Correct 169 ms 3520 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 33884 KB Ok
2 Correct 281 ms 33844 KB Ok
3 Correct 255 ms 33856 KB Ok
4 Correct 253 ms 33908 KB Ok
5 Correct 263 ms 33880 KB Ok
6 Correct 239 ms 33968 KB Ok
7 Correct 282 ms 34152 KB Ok
8 Correct 283 ms 34084 KB Ok
9 Correct 258 ms 34464 KB Ok
10 Correct 280 ms 34024 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 34000 KB Ok
2 Correct 270 ms 34012 KB Ok
3 Correct 271 ms 33916 KB Ok
4 Correct 251 ms 34036 KB Ok
5 Correct 248 ms 34048 KB Ok
6 Correct 271 ms 33900 KB Ok
7 Correct 234 ms 34024 KB Ok
8 Correct 278 ms 33992 KB Ok
9 Correct 254 ms 33920 KB Ok
10 Correct 252 ms 33832 KB Ok
11 Correct 239 ms 33884 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 34048 KB Ok
2 Correct 248 ms 34000 KB Ok
3 Correct 239 ms 33992 KB Ok
4 Correct 266 ms 34032 KB Ok
5 Correct 241 ms 34012 KB Ok
6 Correct 539 ms 38068 KB Ok
7 Correct 469 ms 36440 KB Ok
8 Correct 709 ms 39328 KB Ok
9 Correct 615 ms 39848 KB Ok
10 Correct 430 ms 36332 KB Ok
11 Correct 570 ms 39236 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 34024 KB Ok
2 Correct 276 ms 34000 KB Ok
3 Correct 202 ms 5004 KB Ok
4 Correct 165 ms 7104 KB Ok
5 Correct 171 ms 4888 KB Ok
6 Correct 201 ms 10440 KB Ok
7 Correct 161 ms 4144 KB Ok
8 Correct 177 ms 10540 KB Ok
9 Correct 178 ms 4728 KB Ok
10 Correct 192 ms 18284 KB Ok
11 Correct 193 ms 4108 KB Ok
12 Correct 169 ms 3520 KB Ok
13 Correct 94 ms 34000 KB Ok
14 Correct 270 ms 34012 KB Ok
15 Correct 271 ms 33916 KB Ok
16 Correct 251 ms 34036 KB Ok
17 Correct 248 ms 34048 KB Ok
18 Correct 271 ms 33900 KB Ok
19 Correct 234 ms 34024 KB Ok
20 Correct 278 ms 33992 KB Ok
21 Correct 254 ms 33920 KB Ok
22 Correct 252 ms 33832 KB Ok
23 Correct 239 ms 33884 KB Ok
24 Correct 170 ms 2768 KB Ok
25 Correct 181 ms 3264 KB Ok
26 Correct 177 ms 4824 KB Ok
27 Correct 283 ms 5004 KB Ok
28 Correct 175 ms 3340 KB Ok
29 Correct 172 ms 13276 KB Ok
30 Correct 175 ms 4108 KB Ok
31 Correct 173 ms 3180 KB Ok
32 Correct 184 ms 2992 KB Ok
33 Correct 200 ms 4324 KB Ok
34 Correct 240 ms 34052 KB Ok
35 Correct 278 ms 34188 KB Ok
36 Correct 267 ms 34116 KB Ok
37 Correct 276 ms 34024 KB Ok
38 Correct 290 ms 34052 KB Ok
39 Correct 266 ms 34044 KB Ok
40 Correct 254 ms 33984 KB Ok
41 Correct 297 ms 34068 KB Ok
42 Correct 231 ms 34008 KB Ok
43 Correct 261 ms 34108 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 34024 KB Ok
2 Correct 276 ms 34000 KB Ok
3 Correct 202 ms 5004 KB Ok
4 Correct 165 ms 7104 KB Ok
5 Correct 171 ms 4888 KB Ok
6 Correct 201 ms 10440 KB Ok
7 Correct 161 ms 4144 KB Ok
8 Correct 177 ms 10540 KB Ok
9 Correct 178 ms 4728 KB Ok
10 Correct 192 ms 18284 KB Ok
11 Correct 193 ms 4108 KB Ok
12 Correct 169 ms 3520 KB Ok
13 Correct 243 ms 33884 KB Ok
14 Correct 281 ms 33844 KB Ok
15 Correct 255 ms 33856 KB Ok
16 Correct 253 ms 33908 KB Ok
17 Correct 263 ms 33880 KB Ok
18 Correct 239 ms 33968 KB Ok
19 Correct 282 ms 34152 KB Ok
20 Correct 283 ms 34084 KB Ok
21 Correct 258 ms 34464 KB Ok
22 Correct 280 ms 34024 KB Ok
23 Correct 94 ms 34000 KB Ok
24 Correct 270 ms 34012 KB Ok
25 Correct 271 ms 33916 KB Ok
26 Correct 251 ms 34036 KB Ok
27 Correct 248 ms 34048 KB Ok
28 Correct 271 ms 33900 KB Ok
29 Correct 234 ms 34024 KB Ok
30 Correct 278 ms 33992 KB Ok
31 Correct 254 ms 33920 KB Ok
32 Correct 252 ms 33832 KB Ok
33 Correct 239 ms 33884 KB Ok
34 Correct 170 ms 2768 KB Ok
35 Correct 181 ms 3264 KB Ok
36 Correct 177 ms 4824 KB Ok
37 Correct 283 ms 5004 KB Ok
38 Correct 175 ms 3340 KB Ok
39 Correct 172 ms 13276 KB Ok
40 Correct 175 ms 4108 KB Ok
41 Correct 173 ms 3180 KB Ok
42 Correct 184 ms 2992 KB Ok
43 Correct 200 ms 4324 KB Ok
44 Correct 240 ms 34052 KB Ok
45 Correct 278 ms 34188 KB Ok
46 Correct 267 ms 34116 KB Ok
47 Correct 276 ms 34024 KB Ok
48 Correct 290 ms 34052 KB Ok
49 Correct 266 ms 34044 KB Ok
50 Correct 254 ms 33984 KB Ok
51 Correct 297 ms 34068 KB Ok
52 Correct 231 ms 34008 KB Ok
53 Correct 261 ms 34108 KB Ok
54 Correct 362 ms 4988 KB Ok
55 Correct 366 ms 5440 KB Ok
56 Correct 366 ms 5452 KB Ok
57 Correct 304 ms 4568 KB Ok
58 Correct 359 ms 5348 KB Ok
59 Correct 342 ms 5168 KB Ok
60 Correct 316 ms 4856 KB Ok
61 Correct 313 ms 4696 KB Ok
62 Correct 378 ms 5564 KB Ok
63 Correct 333 ms 5112 KB Ok
64 Correct 366 ms 5408 KB Ok
65 Correct 363 ms 5364 KB Ok
66 Correct 338 ms 4920 KB Ok
67 Correct 310 ms 4704 KB Ok
68 Correct 341 ms 5200 KB Ok
69 Correct 531 ms 40352 KB Ok
70 Correct 591 ms 40704 KB Ok
71 Correct 513 ms 40380 KB Ok
72 Correct 532 ms 40164 KB Ok
73 Correct 526 ms 40548 KB Ok
74 Correct 532 ms 40160 KB Ok
75 Correct 517 ms 40176 KB Ok
76 Correct 531 ms 40496 KB Ok
77 Correct 509 ms 40156 KB Ok
78 Correct 568 ms 40112 KB Ok
79 Correct 573 ms 40596 KB Ok
80 Correct 518 ms 40264 KB Ok
81 Correct 538 ms 40560 KB Ok
82 Correct 519 ms 40272 KB Ok
83 Correct 509 ms 40392 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 34024 KB Ok
2 Correct 276 ms 34000 KB Ok
3 Correct 202 ms 5004 KB Ok
4 Correct 165 ms 7104 KB Ok
5 Correct 171 ms 4888 KB Ok
6 Correct 201 ms 10440 KB Ok
7 Correct 161 ms 4144 KB Ok
8 Correct 177 ms 10540 KB Ok
9 Correct 178 ms 4728 KB Ok
10 Correct 192 ms 18284 KB Ok
11 Correct 193 ms 4108 KB Ok
12 Correct 169 ms 3520 KB Ok
13 Correct 243 ms 33884 KB Ok
14 Correct 281 ms 33844 KB Ok
15 Correct 255 ms 33856 KB Ok
16 Correct 253 ms 33908 KB Ok
17 Correct 263 ms 33880 KB Ok
18 Correct 239 ms 33968 KB Ok
19 Correct 282 ms 34152 KB Ok
20 Correct 283 ms 34084 KB Ok
21 Correct 258 ms 34464 KB Ok
22 Correct 280 ms 34024 KB Ok
23 Correct 94 ms 34000 KB Ok
24 Correct 270 ms 34012 KB Ok
25 Correct 271 ms 33916 KB Ok
26 Correct 251 ms 34036 KB Ok
27 Correct 248 ms 34048 KB Ok
28 Correct 271 ms 33900 KB Ok
29 Correct 234 ms 34024 KB Ok
30 Correct 278 ms 33992 KB Ok
31 Correct 254 ms 33920 KB Ok
32 Correct 252 ms 33832 KB Ok
33 Correct 239 ms 33884 KB Ok
34 Correct 258 ms 34048 KB Ok
35 Correct 248 ms 34000 KB Ok
36 Correct 239 ms 33992 KB Ok
37 Correct 266 ms 34032 KB Ok
38 Correct 241 ms 34012 KB Ok
39 Correct 539 ms 38068 KB Ok
40 Correct 469 ms 36440 KB Ok
41 Correct 709 ms 39328 KB Ok
42 Correct 615 ms 39848 KB Ok
43 Correct 430 ms 36332 KB Ok
44 Correct 570 ms 39236 KB Ok
45 Correct 170 ms 2768 KB Ok
46 Correct 181 ms 3264 KB Ok
47 Correct 177 ms 4824 KB Ok
48 Correct 283 ms 5004 KB Ok
49 Correct 175 ms 3340 KB Ok
50 Correct 172 ms 13276 KB Ok
51 Correct 175 ms 4108 KB Ok
52 Correct 173 ms 3180 KB Ok
53 Correct 184 ms 2992 KB Ok
54 Correct 200 ms 4324 KB Ok
55 Correct 240 ms 34052 KB Ok
56 Correct 278 ms 34188 KB Ok
57 Correct 267 ms 34116 KB Ok
58 Correct 276 ms 34024 KB Ok
59 Correct 290 ms 34052 KB Ok
60 Correct 266 ms 34044 KB Ok
61 Correct 254 ms 33984 KB Ok
62 Correct 297 ms 34068 KB Ok
63 Correct 231 ms 34008 KB Ok
64 Correct 261 ms 34108 KB Ok
65 Correct 362 ms 4988 KB Ok
66 Correct 366 ms 5440 KB Ok
67 Correct 366 ms 5452 KB Ok
68 Correct 304 ms 4568 KB Ok
69 Correct 359 ms 5348 KB Ok
70 Correct 342 ms 5168 KB Ok
71 Correct 316 ms 4856 KB Ok
72 Correct 313 ms 4696 KB Ok
73 Correct 378 ms 5564 KB Ok
74 Correct 333 ms 5112 KB Ok
75 Correct 366 ms 5408 KB Ok
76 Correct 363 ms 5364 KB Ok
77 Correct 338 ms 4920 KB Ok
78 Correct 310 ms 4704 KB Ok
79 Correct 341 ms 5200 KB Ok
80 Correct 531 ms 40352 KB Ok
81 Correct 591 ms 40704 KB Ok
82 Correct 513 ms 40380 KB Ok
83 Correct 532 ms 40164 KB Ok
84 Correct 526 ms 40548 KB Ok
85 Correct 532 ms 40160 KB Ok
86 Correct 517 ms 40176 KB Ok
87 Correct 531 ms 40496 KB Ok
88 Correct 509 ms 40156 KB Ok
89 Correct 568 ms 40112 KB Ok
90 Correct 573 ms 40596 KB Ok
91 Correct 518 ms 40264 KB Ok
92 Correct 538 ms 40560 KB Ok
93 Correct 519 ms 40272 KB Ok
94 Correct 509 ms 40392 KB Ok
95 Correct 630 ms 9404 KB Ok
96 Correct 885 ms 13060 KB Ok
97 Correct 854 ms 11364 KB Ok
98 Correct 699 ms 9256 KB Ok
99 Correct 742 ms 10176 KB Ok
100 Correct 787 ms 11360 KB Ok
101 Correct 801 ms 10668 KB Ok
102 Correct 789 ms 11000 KB Ok
103 Correct 757 ms 11264 KB Ok
104 Correct 879 ms 12012 KB Ok
105 Correct 835 ms 12076 KB Ok
106 Correct 730 ms 10384 KB Ok
107 Correct 811 ms 11508 KB Ok
108 Correct 880 ms 12636 KB Ok
109 Correct 805 ms 11460 KB Ok
110 Correct 1737 ms 54944 KB Ok
111 Correct 1942 ms 56768 KB Ok
112 Correct 1757 ms 57316 KB Ok
113 Correct 1797 ms 55748 KB Ok
114 Correct 1770 ms 57736 KB Ok
115 Correct 1936 ms 56888 KB Ok
116 Correct 1862 ms 57548 KB Ok
117 Correct 1943 ms 56060 KB Ok
118 Execution timed out 2011 ms 57620 KB Time limit exceeded
119 Halted 0 ms 0 KB -