oj.uz

Submission #518703

# Submission time Handle Problem Language Result Execution time Memory
518703 2022-01-24T12:58:21 Z spike1236 Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 42556 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ll long long
#define ld long double
#define all(_v) _v.begin(), _v.end()
#define sz(_v) (int)_v.size()
#define pii pair <int, int>
#define pll pair <ll, ll>
#define veci vector <int>
#define vecll vector <ll>

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const double PI = 3.1415926535897932384626433832795;
const double eps = 1e-9;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;

const int MAXN = 4e5 + 10;
int n, m;
int pref[MAXN];
char used[MAXN];
veci ts;
bool cyc;
veci g[MAXN];

void dfs(int v) {
    if(cyc) return;
    used[v] = 1;
    for(auto to : g[v]) {
        if(!used[to]) dfs(to);
        else if(used[to] == 1) {
            cyc = 1;
            return;
        }
    }
    ts.pb(v);
    used[v] = 2;
}

void solve() {
    cin >> n >> m;
    int l = 1, r = n + m, rs = 0;
    while(l <= r) {
        int mid = l + r >> 1;
        ts.clear();
        for(int i = 0; i <= mid; ++i) g[i].clear(), used[i] = 0;
        cyc = 0;
        for(int i = 0; i <= mid; ++i) {
            if(i + m <= mid) g[i + m].pb(i);
            if(i + n <= mid) g[i].pb(i + n);
        }
        for(int i = 0; i <= mid; ++i) {
          if(!used[i]) dfs(i);
          if(cyc) break;
        }
        if(cyc) r = mid - 1;
        else rs = mid, l = mid + 1;
    }
    cout << rs << '\n';
    ts.clear();
    for(int i = 0; i <= rs; ++i) g[i].clear(), used[i] = 0;
    cyc = 0;
    for(int i = 0; i <= rs; ++i) {
        if(i + m <= rs) g[i].pb(i + m);
        if(i + n <= rs) g[i + n].pb(i);
    }
    for(int i = 0; i <= rs; ++i) if(!used[i]) dfs(i);
    reverse(all(ts));
    for(int i = 0; i < sz(ts); ++i) pref[ts[i]] = i;
    for(int i = 1; i <= rs; ++i) cout << pref[i] - pref[i - 1] << ' ';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int CNT_TESTS = 1;
    cin >> CNT_TESTS;
    for(int NUMCASE = 1; NUMCASE <= CNT_TESTS; ++NUMCASE) {
        solve();
        if(NUMCASE != CNT_TESTS) cout << '\n';
    }
    return 0;
}

Compilation message

sequence.cpp: In function 'void solve()':
sequence.cpp:49:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
6.0 / 6.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Ok
2 Correct 5 ms 9620 KB Ok
3 Correct 5 ms 9676 KB Ok
4 Correct 6 ms 9676 KB Ok
5 Correct 5 ms 9676 KB Ok
6 Correct 12 ms 9920 KB Ok
7 Correct 33 ms 10864 KB Ok
8 Correct 17 ms 10188 KB Ok
9 Correct 38 ms 10948 KB Ok
10 Correct 23 ms 10440 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9660 KB Ok
2 Correct 5 ms 9676 KB Ok
3 Correct 5 ms 9672 KB Ok
4 Correct 5 ms 9712 KB Ok
5 Correct 5 ms 9676 KB Ok
6 Correct 394 ms 26988 KB Ok
7 Correct 328 ms 29116 KB Ok
8 Correct 713 ms 31028 KB Ok
9 Correct 444 ms 29976 KB Ok
10 Correct 244 ms 21512 KB Ok
11 Correct 412 ms 31768 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Ok
2 Correct 5 ms 9676 KB Ok
3 Correct 5 ms 9676 KB Ok
4 Correct 5 ms 9676 KB Ok
5 Correct 5 ms 9676 KB Ok
6 Correct 5 ms 9676 KB Ok
7 Correct 5 ms 9676 KB Ok
8 Correct 5 ms 9716 KB Ok
9 Correct 5 ms 9676 KB Ok
10 Correct 6 ms 9676 KB Ok
11 Correct 6 ms 9708 KB Ok
12 Correct 6 ms 9676 KB Ok
13 Correct 5 ms 9676 KB Ok
14 Correct 5 ms 9676 KB Ok
15 Correct 5 ms 9624 KB Ok
16 Correct 5 ms 9676 KB Ok
17 Correct 6 ms 9676 KB Ok
18 Correct 5 ms 9676 KB Ok
19 Correct 5 ms 9676 KB Ok
20 Correct 5 ms 9676 KB Ok
21 Correct 5 ms 9676 KB Ok
22 Correct 5 ms 9676 KB Ok
23 Correct 5 ms 9676 KB Ok
24 Correct 9 ms 9804 KB Ok
25 Correct 9 ms 9916 KB Ok
26 Correct 10 ms 9844 KB Ok
27 Correct 10 ms 9900 KB Ok
28 Correct 9 ms 9804 KB Ok
29 Correct 8 ms 9804 KB Ok
30 Correct 8 ms 9804 KB Ok
31 Correct 9 ms 9804 KB Ok
32 Correct 9 ms 9888 KB Ok
33 Correct 9 ms 9804 KB Ok
34 Correct 15 ms 10112 KB Ok
35 Correct 15 ms 10188 KB Ok
36 Correct 16 ms 10208 KB Ok
37 Correct 16 ms 10188 KB Ok
38 Correct 16 ms 10188 KB Ok
39 Correct 15 ms 10184 KB Ok
40 Correct 18 ms 10188 KB Ok
41 Correct 15 ms 10128 KB Ok
42 Correct 16 ms 10116 KB Ok
43 Correct 16 ms 10144 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Ok
2 Correct 5 ms 9676 KB Ok
3 Correct 5 ms 9676 KB Ok
4 Correct 5 ms 9676 KB Ok
5 Correct 5 ms 9676 KB Ok
6 Correct 5 ms 9676 KB Ok
7 Correct 5 ms 9676 KB Ok
8 Correct 5 ms 9716 KB Ok
9 Correct 5 ms 9676 KB Ok
10 Correct 6 ms 9676 KB Ok
11 Correct 6 ms 9708 KB Ok
12 Correct 6 ms 9676 KB Ok
13 Correct 5 ms 9676 KB Ok
14 Correct 5 ms 9620 KB Ok
15 Correct 5 ms 9676 KB Ok
16 Correct 6 ms 9676 KB Ok
17 Correct 5 ms 9676 KB Ok
18 Correct 12 ms 9920 KB Ok
19 Correct 33 ms 10864 KB Ok
20 Correct 17 ms 10188 KB Ok
21 Correct 38 ms 10948 KB Ok
22 Correct 23 ms 10440 KB Ok
23 Correct 5 ms 9676 KB Ok
24 Correct 5 ms 9676 KB Ok
25 Correct 5 ms 9624 KB Ok
26 Correct 5 ms 9676 KB Ok
27 Correct 6 ms 9676 KB Ok
28 Correct 5 ms 9676 KB Ok
29 Correct 5 ms 9676 KB Ok
30 Correct 5 ms 9676 KB Ok
31 Correct 5 ms 9676 KB Ok
32 Correct 5 ms 9676 KB Ok
33 Correct 5 ms 9676 KB Ok
34 Correct 9 ms 9804 KB Ok
35 Correct 9 ms 9916 KB Ok
36 Correct 10 ms 9844 KB Ok
37 Correct 10 ms 9900 KB Ok
38 Correct 9 ms 9804 KB Ok
39 Correct 8 ms 9804 KB Ok
40 Correct 8 ms 9804 KB Ok
41 Correct 9 ms 9804 KB Ok
42 Correct 9 ms 9888 KB Ok
43 Correct 9 ms 9804 KB Ok
44 Correct 15 ms 10112 KB Ok
45 Correct 15 ms 10188 KB Ok
46 Correct 16 ms 10208 KB Ok
47 Correct 16 ms 10188 KB Ok
48 Correct 16 ms 10188 KB Ok
49 Correct 15 ms 10184 KB Ok
50 Correct 18 ms 10188 KB Ok
51 Correct 15 ms 10128 KB Ok
52 Correct 16 ms 10116 KB Ok
53 Correct 16 ms 10144 KB Ok
54 Correct 226 ms 15516 KB Ok
55 Correct 266 ms 15908 KB Ok
56 Correct 268 ms 15872 KB Ok
57 Correct 199 ms 14936 KB Ok
58 Correct 225 ms 15812 KB Ok
59 Correct 208 ms 15432 KB Ok
60 Correct 191 ms 14956 KB Ok
61 Correct 184 ms 15220 KB Ok
62 Correct 268 ms 16116 KB Ok
63 Correct 212 ms 15236 KB Ok
64 Correct 275 ms 15948 KB Ok
65 Correct 234 ms 15704 KB Ok
66 Correct 215 ms 15432 KB Ok
67 Correct 202 ms 15048 KB Ok
68 Correct 221 ms 15684 KB Ok
69 Correct 666 ms 24516 KB Ok
70 Correct 804 ms 24944 KB Ok
71 Correct 679 ms 24612 KB Ok
72 Correct 676 ms 24396 KB Ok
73 Correct 716 ms 24812 KB Ok
74 Correct 657 ms 24588 KB Ok
75 Correct 677 ms 24376 KB Ok
76 Correct 817 ms 24824 KB Ok
77 Correct 641 ms 24556 KB Ok
78 Correct 740 ms 24348 KB Ok
79 Correct 755 ms 24848 KB Ok
80 Correct 654 ms 24400 KB Ok
81 Correct 778 ms 25004 KB Ok
82 Correct 666 ms 24672 KB Ok
83 Correct 632 ms 24720 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Ok
2 Correct 5 ms 9676 KB Ok
3 Correct 5 ms 9676 KB Ok
4 Correct 5 ms 9676 KB Ok
5 Correct 5 ms 9676 KB Ok
6 Correct 5 ms 9676 KB Ok
7 Correct 5 ms 9676 KB Ok
8 Correct 5 ms 9716 KB Ok
9 Correct 5 ms 9676 KB Ok
10 Correct 6 ms 9676 KB Ok
11 Correct 6 ms 9708 KB Ok
12 Correct 6 ms 9676 KB Ok
13 Correct 5 ms 9676 KB Ok
14 Correct 5 ms 9620 KB Ok
15 Correct 5 ms 9676 KB Ok
16 Correct 6 ms 9676 KB Ok
17 Correct 5 ms 9676 KB Ok
18 Correct 12 ms 9920 KB Ok
19 Correct 33 ms 10864 KB Ok
20 Correct 17 ms 10188 KB Ok
21 Correct 38 ms 10948 KB Ok
22 Correct 23 ms 10440 KB Ok
23 Correct 5 ms 9676 KB Ok
24 Correct 5 ms 9676 KB Ok
25 Correct 5 ms 9624 KB Ok
26 Correct 5 ms 9676 KB Ok
27 Correct 6 ms 9676 KB Ok
28 Correct 5 ms 9676 KB Ok
29 Correct 5 ms 9676 KB Ok
30 Correct 5 ms 9676 KB Ok
31 Correct 5 ms 9676 KB Ok
32 Correct 5 ms 9676 KB Ok
33 Correct 5 ms 9676 KB Ok
34 Correct 5 ms 9660 KB Ok
35 Correct 5 ms 9676 KB Ok
36 Correct 5 ms 9672 KB Ok
37 Correct 5 ms 9712 KB Ok
38 Correct 5 ms 9676 KB Ok
39 Correct 394 ms 26988 KB Ok
40 Correct 328 ms 29116 KB Ok
41 Correct 713 ms 31028 KB Ok
42 Correct 444 ms 29976 KB Ok
43 Correct 244 ms 21512 KB Ok
44 Correct 412 ms 31768 KB Ok
45 Correct 9 ms 9804 KB Ok
46 Correct 9 ms 9916 KB Ok
47 Correct 10 ms 9844 KB Ok
48 Correct 10 ms 9900 KB Ok
49 Correct 9 ms 9804 KB Ok
50 Correct 8 ms 9804 KB Ok
51 Correct 8 ms 9804 KB Ok
52 Correct 9 ms 9804 KB Ok
53 Correct 9 ms 9888 KB Ok
54 Correct 9 ms 9804 KB Ok
55 Correct 15 ms 10112 KB Ok
56 Correct 15 ms 10188 KB Ok
57 Correct 16 ms 10208 KB Ok
58 Correct 16 ms 10188 KB Ok
59 Correct 16 ms 10188 KB Ok
60 Correct 15 ms 10184 KB Ok
61 Correct 18 ms 10188 KB Ok
62 Correct 15 ms 10128 KB Ok
63 Correct 16 ms 10116 KB Ok
64 Correct 16 ms 10144 KB Ok
65 Correct 226 ms 15516 KB Ok
66 Correct 266 ms 15908 KB Ok
67 Correct 268 ms 15872 KB Ok
68 Correct 199 ms 14936 KB Ok
69 Correct 225 ms 15812 KB Ok
70 Correct 208 ms 15432 KB Ok
71 Correct 191 ms 14956 KB Ok
72 Correct 184 ms 15220 KB Ok
73 Correct 268 ms 16116 KB Ok
74 Correct 212 ms 15236 KB Ok
75 Correct 275 ms 15948 KB Ok
76 Correct 234 ms 15704 KB Ok
77 Correct 215 ms 15432 KB Ok
78 Correct 202 ms 15048 KB Ok
79 Correct 221 ms 15684 KB Ok
80 Correct 666 ms 24516 KB Ok
81 Correct 804 ms 24944 KB Ok
82 Correct 679 ms 24612 KB Ok
83 Correct 676 ms 24396 KB Ok
84 Correct 716 ms 24812 KB Ok
85 Correct 657 ms 24588 KB Ok
86 Correct 677 ms 24376 KB Ok
87 Correct 817 ms 24824 KB Ok
88 Correct 641 ms 24556 KB Ok
89 Correct 740 ms 24348 KB Ok
90 Correct 755 ms 24848 KB Ok
91 Correct 654 ms 24400 KB Ok
92 Correct 778 ms 25004 KB Ok
93 Correct 666 ms 24672 KB Ok
94 Correct 632 ms 24720 KB Ok
95 Correct 686 ms 25024 KB Ok
96 Correct 919 ms 32576 KB Ok
97 Correct 863 ms 29104 KB Ok
98 Correct 618 ms 28280 KB Ok
99 Correct 776 ms 27952 KB Ok
100 Correct 811 ms 28372 KB Ok
101 Correct 850 ms 30208 KB Ok
102 Correct 817 ms 28716 KB Ok
103 Correct 787 ms 30160 KB Ok
104 Correct 1145 ms 31448 KB Ok
105 Correct 945 ms 32128 KB Ok
106 Correct 816 ms 30956 KB Ok
107 Correct 910 ms 30804 KB Ok
108 Correct 1064 ms 32168 KB Ok
109 Correct 1004 ms 32412 KB Ok
110 Execution timed out 2076 ms 42556 KB Time limit exceeded
111 Halted 0 ms 0 KB -