답안 #737069

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
737069	2023-05-06T14:26:03 Z	GrindMachine	Nice sequence (IZhO18_sequence)	C++17	100 / 100	1643 ms	57416 KB

sequence

// 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 + 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:151:5: note: in expansion of macro 'rep'
  151 |     rep(i, sz(topo)) {
      |     ^~~

Subtask #1

6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	468 KB	Ok
2	Correct	1 ms	564 KB	Ok
3	Correct	1 ms	568 KB	Ok
4	Correct	1 ms	468 KB	Ok
5	Correct	1 ms	468 KB	Ok
6	Correct	1 ms	468 KB	Ok
7	Correct	1 ms	560 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
12	Correct	1 ms	568 KB	Ok

Subtask #2

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	468 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	560 KB	Ok
6	Correct	5 ms	724 KB	Ok
7	Correct	23 ms	1468 KB	Ok
8	Correct	11 ms	1020 KB	Ok
9	Correct	27 ms	1756 KB	Ok
10	Correct	15 ms	1200 KB	Ok

Subtask #3

14.0 / 14.0

#	결과	실행 시간	메모리	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	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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	560 KB	Ok
2	Correct	1 ms	564 KB	Ok
3	Correct	1 ms	468 KB	Ok
4	Correct	1 ms	560 KB	Ok
5	Correct	1 ms	468 KB	Ok
6	Correct	282 ms	14728 KB	Ok
7	Correct	226 ms	16284 KB	Ok
8	Correct	468 ms	18392 KB	Ok
9	Correct	331 ms	18364 KB	Ok
10	Correct	227 ms	10024 KB	Ok
11	Correct	342 ms	19168 KB	Ok

Subtask #5

14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	468 KB	Ok
2	Correct	1 ms	564 KB	Ok
3	Correct	1 ms	568 KB	Ok
4	Correct	1 ms	468 KB	Ok
5	Correct	1 ms	468 KB	Ok
6	Correct	1 ms	468 KB	Ok
7	Correct	1 ms	560 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
12	Correct	1 ms	568 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	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	5 ms	560 KB	Ok
26	Correct	5 ms	660 KB	Ok
27	Correct	5 ms	596 KB	Ok
28	Correct	4 ms	596 KB	Ok
29	Correct	4 ms	664 KB	Ok
30	Correct	4 ms	596 KB	Ok
31	Correct	5 ms	564 KB	Ok
32	Correct	5 ms	608 KB	Ok
33	Correct	4 ms	596 KB	Ok
34	Correct	9 ms	980 KB	Ok
35	Correct	8 ms	952 KB	Ok
36	Correct	9 ms	980 KB	Ok
37	Correct	8 ms	980 KB	Ok
38	Correct	9 ms	988 KB	Ok
39	Correct	10 ms	948 KB	Ok
40	Correct	9 ms	980 KB	Ok
41	Correct	8 ms	972 KB	Ok
42	Correct	9 ms	980 KB	Ok
43	Correct	9 ms	980 KB	Ok

Subtask #6

18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	468 KB	Ok
2	Correct	1 ms	564 KB	Ok
3	Correct	1 ms	568 KB	Ok
4	Correct	1 ms	468 KB	Ok
5	Correct	1 ms	468 KB	Ok
6	Correct	1 ms	468 KB	Ok
7	Correct	1 ms	560 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
12	Correct	1 ms	568 KB	Ok
13	Correct	1 ms	468 KB	Ok
14	Correct	1 ms	560 KB	Ok
15	Correct	1 ms	564 KB	Ok
16	Correct	1 ms	468 KB	Ok
17	Correct	1 ms	560 KB	Ok
18	Correct	5 ms	724 KB	Ok
19	Correct	23 ms	1468 KB	Ok
20	Correct	11 ms	1020 KB	Ok
21	Correct	27 ms	1756 KB	Ok
22	Correct	15 ms	1200 KB	Ok
23	Correct	1 ms	468 KB	Ok
24	Correct	1 ms	468 KB	Ok
25	Correct	1 ms	468 KB	Ok
26	Correct	1 ms	468 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	5 ms	560 KB	Ok
36	Correct	5 ms	660 KB	Ok
37	Correct	5 ms	596 KB	Ok
38	Correct	4 ms	596 KB	Ok
39	Correct	4 ms	664 KB	Ok
40	Correct	4 ms	596 KB	Ok
41	Correct	5 ms	564 KB	Ok
42	Correct	5 ms	608 KB	Ok
43	Correct	4 ms	596 KB	Ok
44	Correct	9 ms	980 KB	Ok
45	Correct	8 ms	952 KB	Ok
46	Correct	9 ms	980 KB	Ok
47	Correct	8 ms	980 KB	Ok
48	Correct	9 ms	988 KB	Ok
49	Correct	10 ms	948 KB	Ok
50	Correct	9 ms	980 KB	Ok
51	Correct	8 ms	972 KB	Ok
52	Correct	9 ms	980 KB	Ok
53	Correct	9 ms	980 KB	Ok
54	Correct	194 ms	3392 KB	Ok
55	Correct	223 ms	3864 KB	Ok
56	Correct	224 ms	3780 KB	Ok
57	Correct	167 ms	2904 KB	Ok
58	Correct	200 ms	3632 KB	Ok
59	Correct	196 ms	3516 KB	Ok
60	Correct	169 ms	3172 KB	Ok
61	Correct	170 ms	3108 KB	Ok
62	Correct	229 ms	4128 KB	Ok
63	Correct	186 ms	3436 KB	Ok
64	Correct	223 ms	3804 KB	Ok
65	Correct	215 ms	3676 KB	Ok
66	Correct	185 ms	3316 KB	Ok
67	Correct	166 ms	3140 KB	Ok
68	Correct	194 ms	3552 KB	Ok
69	Correct	327 ms	13840 KB	Ok
70	Correct	319 ms	14096 KB	Ok
71	Correct	330 ms	13724 KB	Ok
72	Correct	327 ms	13584 KB	Ok
73	Correct	326 ms	14016 KB	Ok
74	Correct	318 ms	13612 KB	Ok
75	Correct	331 ms	13568 KB	Ok
76	Correct	345 ms	13752 KB	Ok
77	Correct	348 ms	13628 KB	Ok
78	Correct	338 ms	13656 KB	Ok
79	Correct	332 ms	14052 KB	Ok
80	Correct	335 ms	13596 KB	Ok
81	Correct	321 ms	14020 KB	Ok
82	Correct	317 ms	13736 KB	Ok
83	Correct	322 ms	13756 KB	Ok

Subtask #7

24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	468 KB	Ok
2	Correct	1 ms	564 KB	Ok
3	Correct	1 ms	568 KB	Ok
4	Correct	1 ms	468 KB	Ok
5	Correct	1 ms	468 KB	Ok
6	Correct	1 ms	468 KB	Ok
7	Correct	1 ms	560 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
12	Correct	1 ms	568 KB	Ok
13	Correct	1 ms	468 KB	Ok
14	Correct	1 ms	560 KB	Ok
15	Correct	1 ms	564 KB	Ok
16	Correct	1 ms	468 KB	Ok
17	Correct	1 ms	560 KB	Ok
18	Correct	5 ms	724 KB	Ok
19	Correct	23 ms	1468 KB	Ok
20	Correct	11 ms	1020 KB	Ok
21	Correct	27 ms	1756 KB	Ok
22	Correct	15 ms	1200 KB	Ok
23	Correct	1 ms	468 KB	Ok
24	Correct	1 ms	468 KB	Ok
25	Correct	1 ms	468 KB	Ok
26	Correct	1 ms	468 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	560 KB	Ok
35	Correct	1 ms	564 KB	Ok
36	Correct	1 ms	468 KB	Ok
37	Correct	1 ms	560 KB	Ok
38	Correct	1 ms	468 KB	Ok
39	Correct	282 ms	14728 KB	Ok
40	Correct	226 ms	16284 KB	Ok
41	Correct	468 ms	18392 KB	Ok
42	Correct	331 ms	18364 KB	Ok
43	Correct	227 ms	10024 KB	Ok
44	Correct	342 ms	19168 KB	Ok
45	Correct	5 ms	596 KB	Ok
46	Correct	5 ms	560 KB	Ok
47	Correct	5 ms	660 KB	Ok
48	Correct	5 ms	596 KB	Ok
49	Correct	4 ms	596 KB	Ok
50	Correct	4 ms	664 KB	Ok
51	Correct	4 ms	596 KB	Ok
52	Correct	5 ms	564 KB	Ok
53	Correct	5 ms	608 KB	Ok
54	Correct	4 ms	596 KB	Ok
55	Correct	9 ms	980 KB	Ok
56	Correct	8 ms	952 KB	Ok
57	Correct	9 ms	980 KB	Ok
58	Correct	8 ms	980 KB	Ok
59	Correct	9 ms	988 KB	Ok
60	Correct	10 ms	948 KB	Ok
61	Correct	9 ms	980 KB	Ok
62	Correct	8 ms	972 KB	Ok
63	Correct	9 ms	980 KB	Ok
64	Correct	9 ms	980 KB	Ok
65	Correct	194 ms	3392 KB	Ok
66	Correct	223 ms	3864 KB	Ok
67	Correct	224 ms	3780 KB	Ok
68	Correct	167 ms	2904 KB	Ok
69	Correct	200 ms	3632 KB	Ok
70	Correct	196 ms	3516 KB	Ok
71	Correct	169 ms	3172 KB	Ok
72	Correct	170 ms	3108 KB	Ok
73	Correct	229 ms	4128 KB	Ok
74	Correct	186 ms	3436 KB	Ok
75	Correct	223 ms	3804 KB	Ok
76	Correct	215 ms	3676 KB	Ok
77	Correct	185 ms	3316 KB	Ok
78	Correct	166 ms	3140 KB	Ok
79	Correct	194 ms	3552 KB	Ok
80	Correct	327 ms	13840 KB	Ok
81	Correct	319 ms	14096 KB	Ok
82	Correct	330 ms	13724 KB	Ok
83	Correct	327 ms	13584 KB	Ok
84	Correct	326 ms	14016 KB	Ok
85	Correct	318 ms	13612 KB	Ok
86	Correct	331 ms	13568 KB	Ok
87	Correct	345 ms	13752 KB	Ok
88	Correct	348 ms	13628 KB	Ok
89	Correct	338 ms	13656 KB	Ok
90	Correct	332 ms	14052 KB	Ok
91	Correct	335 ms	13596 KB	Ok
92	Correct	321 ms	14020 KB	Ok
93	Correct	317 ms	13736 KB	Ok
94	Correct	322 ms	13756 KB	Ok
95	Correct	512 ms	8128 KB	Ok
96	Correct	759 ms	12408 KB	Ok
97	Correct	725 ms	10580 KB	Ok
98	Correct	568 ms	8500 KB	Ok
99	Correct	661 ms	9368 KB	Ok
100	Correct	675 ms	10360 KB	Ok
101	Correct	689 ms	9976 KB	Ok
102	Correct	676 ms	10192 KB	Ok
103	Correct	683 ms	10468 KB	Ok
104	Correct	840 ms	11312 KB	Ok
105	Correct	730 ms	11644 KB	Ok
106	Correct	630 ms	9868 KB	Ok
107	Correct	726 ms	10724 KB	Ok
108	Correct	779 ms	11836 KB	Ok
109	Correct	690 ms	11044 KB	Ok
110	Correct	1450 ms	54680 KB	Ok
111	Correct	1480 ms	56384 KB	Ok
112	Correct	1447 ms	56760 KB	Ok
113	Correct	1431 ms	55240 KB	Ok
114	Correct	1441 ms	57192 KB	Ok
115	Correct	1443 ms	56656 KB	Ok
116	Correct	1470 ms	57184 KB	Ok
117	Correct	1433 ms	55624 KB	Ok
118	Correct	1417 ms	57416 KB	Ok
119	Correct	1440 ms	55296 KB	Ok
120	Correct	1434 ms	55964 KB	Ok
121	Correct	1426 ms	55516 KB	Ok
122	Correct	1402 ms	56016 KB	Ok
123	Correct	1414 ms	56564 KB	Ok
124	Correct	1458 ms	57024 KB	Ok
125	Correct	1643 ms	39024 KB	Ok