oj.uz

Submission #737058

# Submission time Handle Problem Language Result Execution time Memory
737058 2023-05-06T14:06:29 Z GrindMachine Nice sequence (IZhO18_sequence) C++17
58 / 100
 2000 ms 73888 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

*/

const int MOD = 1e9 + 7;
const int N = 1e6 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

vector<ll> adj[N];
vector<bool> vis(N), recstack(N);
vector<ll> topo;
bool cyc;

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

    trav(v, adj[u]) {
        if (vis[v]) {
            if (recstack[v]) cyc = true;
            conts;
        }

        dfs(v);
    }

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

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

    auto ok = [&](ll mid) {
        rep(i, mid + 1) adj[i].clear(), vis[i] = 0;

        rep1(i, mid) {
            if (i - n >= 0) {
                adj[i].pb(i - n);
            }

            if (i - m >= 0) {
                adj[i - m].pb(i);
            }
        }

        topo.clear();
        cyc = false;

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

        reverse(all(topo));

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

    ll l = 1, r = N - 1;
    ll ans = 0;

    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (ok(mid)) {
            ans = mid;
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }

    ok(ans);

    vector<ll> p(ans + 5);
    rep(i, sz(topo)) {
        p[topo[i]] = i;
    }

    cout << ans << endl;

    rep1(i, ans) {
        ll v = p[i] - p[i - 1];
        cout << v << " ";
    }

    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<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 | #define rep(i, n) for(int i = 0; i < n; ++i)
      |                                    ^
sequence.cpp:134:5: note: in expansion of macro 'rep'
  134 |     rep(i, sz(topo)) {
      |     ^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 67360 KB Ok
2 Correct 457 ms 67372 KB Ok
3 Correct 597 ms 45616 KB Ok
4 Correct 475 ms 47024 KB Ok
5 Correct 624 ms 45424 KB Ok
6 Correct 420 ms 49604 KB Ok
7 Correct 466 ms 44840 KB Ok
8 Correct 461 ms 49692 KB Ok
9 Correct 458 ms 45264 KB Ok
10 Correct 454 ms 55464 KB Ok
11 Correct 489 ms 44836 KB Ok
12 Correct 424 ms 44464 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 67128 KB Ok
2 Correct 433 ms 67128 KB Ok
3 Correct 524 ms 67120 KB Ok
4 Correct 497 ms 67156 KB Ok
5 Correct 520 ms 67120 KB Ok
6 Correct 424 ms 67388 KB Ok
7 Correct 437 ms 67444 KB Ok
8 Correct 440 ms 67424 KB Ok
9 Correct 449 ms 67608 KB Ok
10 Correct 451 ms 67320 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 67312 KB Ok
2 Correct 436 ms 67364 KB Ok
3 Correct 438 ms 67120 KB Ok
4 Correct 410 ms 67336 KB Ok
5 Correct 441 ms 67388 KB Ok
6 Correct 426 ms 67200 KB Ok
7 Correct 425 ms 67364 KB Ok
8 Correct 470 ms 67300 KB Ok
9 Correct 461 ms 67136 KB Ok
10 Correct 440 ms 67192 KB Ok
11 Correct 459 ms 67128 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 67388 KB Ok
2 Correct 453 ms 67316 KB Ok
3 Correct 496 ms 67388 KB Ok
4 Correct 494 ms 67384 KB Ok
5 Correct 537 ms 67312 KB Ok
6 Correct 953 ms 72124 KB Ok
7 Correct 772 ms 70604 KB Ok
8 Correct 1207 ms 73332 KB Ok
9 Correct 924 ms 73888 KB Ok
10 Correct 650 ms 70304 KB Ok
11 Correct 945 ms 73356 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 67360 KB Ok
2 Correct 457 ms 67372 KB Ok
3 Correct 597 ms 45616 KB Ok
4 Correct 475 ms 47024 KB Ok
5 Correct 624 ms 45424 KB Ok
6 Correct 420 ms 49604 KB Ok
7 Correct 466 ms 44840 KB Ok
8 Correct 461 ms 49692 KB Ok
9 Correct 458 ms 45264 KB Ok
10 Correct 454 ms 55464 KB Ok
11 Correct 489 ms 44836 KB Ok
12 Correct 424 ms 44464 KB Ok
13 Correct 166 ms 67312 KB Ok
14 Correct 436 ms 67364 KB Ok
15 Correct 438 ms 67120 KB Ok
16 Correct 410 ms 67336 KB Ok
17 Correct 441 ms 67388 KB Ok
18 Correct 426 ms 67200 KB Ok
19 Correct 425 ms 67364 KB Ok
20 Correct 470 ms 67300 KB Ok
21 Correct 461 ms 67136 KB Ok
22 Correct 440 ms 67192 KB Ok
23 Correct 459 ms 67128 KB Ok
24 Correct 611 ms 43916 KB Ok
25 Correct 700 ms 44332 KB Ok
26 Correct 619 ms 45464 KB Ok
27 Correct 801 ms 45536 KB Ok
28 Correct 644 ms 44184 KB Ok
29 Correct 638 ms 51504 KB Ok
30 Correct 633 ms 44856 KB Ok
31 Correct 688 ms 44156 KB Ok
32 Correct 681 ms 44168 KB Ok
33 Correct 691 ms 45152 KB Ok
34 Correct 1230 ms 67424 KB Ok
35 Correct 697 ms 67388 KB Ok
36 Correct 1097 ms 67336 KB Ok
37 Correct 786 ms 67504 KB Ok
38 Correct 809 ms 67352 KB Ok
39 Correct 1214 ms 67216 KB Ok
40 Correct 927 ms 67384 KB Ok
41 Correct 783 ms 67260 KB Ok
42 Correct 1272 ms 67292 KB Ok
43 Correct 882 ms 67428 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 67360 KB Ok
2 Correct 457 ms 67372 KB Ok
3 Correct 597 ms 45616 KB Ok
4 Correct 475 ms 47024 KB Ok
5 Correct 624 ms 45424 KB Ok
6 Correct 420 ms 49604 KB Ok
7 Correct 466 ms 44840 KB Ok
8 Correct 461 ms 49692 KB Ok
9 Correct 458 ms 45264 KB Ok
10 Correct 454 ms 55464 KB Ok
11 Correct 489 ms 44836 KB Ok
12 Correct 424 ms 44464 KB Ok
13 Correct 421 ms 67128 KB Ok
14 Correct 433 ms 67128 KB Ok
15 Correct 524 ms 67120 KB Ok
16 Correct 497 ms 67156 KB Ok
17 Correct 520 ms 67120 KB Ok
18 Correct 424 ms 67388 KB Ok
19 Correct 437 ms 67444 KB Ok
20 Correct 440 ms 67424 KB Ok
21 Correct 449 ms 67608 KB Ok
22 Correct 451 ms 67320 KB Ok
23 Correct 166 ms 67312 KB Ok
24 Correct 436 ms 67364 KB Ok
25 Correct 438 ms 67120 KB Ok
26 Correct 410 ms 67336 KB Ok
27 Correct 441 ms 67388 KB Ok
28 Correct 426 ms 67200 KB Ok
29 Correct 425 ms 67364 KB Ok
30 Correct 470 ms 67300 KB Ok
31 Correct 461 ms 67136 KB Ok
32 Correct 440 ms 67192 KB Ok
33 Correct 459 ms 67128 KB Ok
34 Correct 611 ms 43916 KB Ok
35 Correct 700 ms 44332 KB Ok
36 Correct 619 ms 45464 KB Ok
37 Correct 801 ms 45536 KB Ok
38 Correct 644 ms 44184 KB Ok
39 Correct 638 ms 51504 KB Ok
40 Correct 633 ms 44856 KB Ok
41 Correct 688 ms 44156 KB Ok
42 Correct 681 ms 44168 KB Ok
43 Correct 691 ms 45152 KB Ok
44 Correct 1230 ms 67424 KB Ok
45 Correct 697 ms 67388 KB Ok
46 Correct 1097 ms 67336 KB Ok
47 Correct 786 ms 67504 KB Ok
48 Correct 809 ms 67352 KB Ok
49 Correct 1214 ms 67216 KB Ok
50 Correct 927 ms 67384 KB Ok
51 Correct 783 ms 67260 KB Ok
52 Correct 1272 ms 67292 KB Ok
53 Correct 882 ms 67428 KB Ok
54 Correct 761 ms 46520 KB Ok
55 Correct 902 ms 46888 KB Ok
56 Correct 829 ms 46812 KB Ok
57 Correct 608 ms 46004 KB Ok
58 Correct 805 ms 46716 KB Ok
59 Correct 732 ms 46560 KB Ok
60 Correct 626 ms 46220 KB Ok
61 Correct 659 ms 46228 KB Ok
62 Correct 901 ms 47116 KB Ok
63 Correct 694 ms 46352 KB Ok
64 Correct 842 ms 47000 KB Ok
65 Correct 780 ms 46776 KB Ok
66 Correct 687 ms 46360 KB Ok
67 Correct 619 ms 46176 KB Ok
68 Correct 711 ms 46732 KB Ok
69 Execution timed out 2056 ms 72876 KB Time limit exceeded
70 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 67360 KB Ok
2 Correct 457 ms 67372 KB Ok
3 Correct 597 ms 45616 KB Ok
4 Correct 475 ms 47024 KB Ok
5 Correct 624 ms 45424 KB Ok
6 Correct 420 ms 49604 KB Ok
7 Correct 466 ms 44840 KB Ok
8 Correct 461 ms 49692 KB Ok
9 Correct 458 ms 45264 KB Ok
10 Correct 454 ms 55464 KB Ok
11 Correct 489 ms 44836 KB Ok
12 Correct 424 ms 44464 KB Ok
13 Correct 421 ms 67128 KB Ok
14 Correct 433 ms 67128 KB Ok
15 Correct 524 ms 67120 KB Ok
16 Correct 497 ms 67156 KB Ok
17 Correct 520 ms 67120 KB Ok
18 Correct 424 ms 67388 KB Ok
19 Correct 437 ms 67444 KB Ok
20 Correct 440 ms 67424 KB Ok
21 Correct 449 ms 67608 KB Ok
22 Correct 451 ms 67320 KB Ok
23 Correct 166 ms 67312 KB Ok
24 Correct 436 ms 67364 KB Ok
25 Correct 438 ms 67120 KB Ok
26 Correct 410 ms 67336 KB Ok
27 Correct 441 ms 67388 KB Ok
28 Correct 426 ms 67200 KB Ok
29 Correct 425 ms 67364 KB Ok
30 Correct 470 ms 67300 KB Ok
31 Correct 461 ms 67136 KB Ok
32 Correct 440 ms 67192 KB Ok
33 Correct 459 ms 67128 KB Ok
34 Correct 429 ms 67388 KB Ok
35 Correct 453 ms 67316 KB Ok
36 Correct 496 ms 67388 KB Ok
37 Correct 494 ms 67384 KB Ok
38 Correct 537 ms 67312 KB Ok
39 Correct 953 ms 72124 KB Ok
40 Correct 772 ms 70604 KB Ok
41 Correct 1207 ms 73332 KB Ok
42 Correct 924 ms 73888 KB Ok
43 Correct 650 ms 70304 KB Ok
44 Correct 945 ms 73356 KB Ok
45 Correct 611 ms 43916 KB Ok
46 Correct 700 ms 44332 KB Ok
47 Correct 619 ms 45464 KB Ok
48 Correct 801 ms 45536 KB Ok
49 Correct 644 ms 44184 KB Ok
50 Correct 638 ms 51504 KB Ok
51 Correct 633 ms 44856 KB Ok
52 Correct 688 ms 44156 KB Ok
53 Correct 681 ms 44168 KB Ok
54 Correct 691 ms 45152 KB Ok
55 Correct 1230 ms 67424 KB Ok
56 Correct 697 ms 67388 KB Ok
57 Correct 1097 ms 67336 KB Ok
58 Correct 786 ms 67504 KB Ok
59 Correct 809 ms 67352 KB Ok
60 Correct 1214 ms 67216 KB Ok
61 Correct 927 ms 67384 KB Ok
62 Correct 783 ms 67260 KB Ok
63 Correct 1272 ms 67292 KB Ok
64 Correct 882 ms 67428 KB Ok
65 Correct 761 ms 46520 KB Ok
66 Correct 902 ms 46888 KB Ok
67 Correct 829 ms 46812 KB Ok
68 Correct 608 ms 46004 KB Ok
69 Correct 805 ms 46716 KB Ok
70 Correct 732 ms 46560 KB Ok
71 Correct 626 ms 46220 KB Ok
72 Correct 659 ms 46228 KB Ok
73 Correct 901 ms 47116 KB Ok
74 Correct 694 ms 46352 KB Ok
75 Correct 842 ms 47000 KB Ok
76 Correct 780 ms 46776 KB Ok
77 Correct 687 ms 46360 KB Ok
78 Correct 619 ms 46176 KB Ok
79 Correct 711 ms 46732 KB Ok
80 Execution timed out 2056 ms 72876 KB Time limit exceeded
81 Halted 0 ms 0 KB -