oj.uz

Submission #518708

# Submission time Handle Problem Language Result Execution time Memory
518708 2022-01-24T13:03:29 Z spike1236 Nice sequence (IZhO18_sequence) C++14
100 / 100
 1199 ms 57588 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];
bool cyc;
int cur;
veci ts;

void dfs(int v) {
    if(cyc) return;
    used[v] = 1;
    for(auto to : {v - n, v + m}) {
        if(to < 0 || to > cur) continue;
        if(!used[to]) dfs(to);
        else if(used[to] == 1) {
            cyc = 1;
            return;
        }
    }
    used[v] = 2;
}

void dfs2(int v) {
    used[v] = 1;
    for(auto to : {v - n, v + m}) {
        if(to < 0 || to > cur) continue;
        if(!used[to]) dfs2(to);
    }
    ts.pb(v);
}

void solve() {
    cin >> n >> m;
    int l = 1, r = n + m, rs = 0;
    while(l <= r) {
        int mid = l + r >> 1;
        cur = mid;
        for(int i = 0; i <= mid; ++i) used[i] = 0;
        cyc = 0;
        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) used[i] = 0;
    for(int i = 0; i <= rs; ++i) if(!used[i]) dfs2(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:58:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
6.0 / 6.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Ok
2 Correct 0 ms 204 KB Ok
3 Correct 1 ms 204 KB Ok
4 Correct 1 ms 284 KB Ok
5 Correct 1 ms 204 KB Ok
6 Correct 3 ms 460 KB Ok
7 Correct 15 ms 1336 KB Ok
8 Correct 6 ms 716 KB Ok
9 Correct 17 ms 1484 KB Ok
10 Correct 9 ms 972 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Ok
2 Correct 0 ms 204 KB Ok
3 Correct 1 ms 204 KB Ok
4 Correct 1 ms 204 KB Ok
5 Correct 1 ms 204 KB Ok
6 Correct 174 ms 14756 KB Ok
7 Correct 148 ms 16668 KB Ok
8 Correct 278 ms 18456 KB Ok
9 Correct 210 ms 18120 KB Ok
10 Correct 138 ms 9968 KB Ok
11 Correct 242 ms 19304 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Ok
2 Correct 0 ms 204 KB Ok
3 Correct 0 ms 204 KB Ok
4 Correct 0 ms 204 KB Ok
5 Correct 1 ms 204 KB Ok
6 Correct 1 ms 204 KB Ok
7 Correct 1 ms 204 KB Ok
8 Correct 1 ms 204 KB Ok
9 Correct 1 ms 204 KB Ok
10 Correct 0 ms 204 KB Ok
11 Correct 0 ms 204 KB Ok
12 Correct 0 ms 204 KB Ok
13 Correct 0 ms 204 KB Ok
14 Correct 0 ms 204 KB Ok
15 Correct 1 ms 204 KB Ok
16 Correct 1 ms 204 KB Ok
17 Correct 1 ms 204 KB Ok
18 Correct 0 ms 204 KB Ok
19 Correct 1 ms 204 KB Ok
20 Correct 1 ms 204 KB Ok
21 Correct 1 ms 204 KB Ok
22 Correct 1 ms 204 KB Ok
23 Correct 0 ms 204 KB Ok
24 Correct 3 ms 332 KB Ok
25 Correct 3 ms 332 KB Ok
26 Correct 3 ms 384 KB Ok
27 Correct 3 ms 332 KB Ok
28 Correct 2 ms 332 KB Ok
29 Correct 2 ms 332 KB Ok
30 Correct 2 ms 332 KB Ok
31 Correct 3 ms 332 KB Ok
32 Correct 3 ms 332 KB Ok
33 Correct 2 ms 332 KB Ok
34 Correct 8 ms 716 KB Ok
35 Correct 6 ms 716 KB Ok
36 Correct 6 ms 716 KB Ok
37 Correct 6 ms 716 KB Ok
38 Correct 7 ms 716 KB Ok
39 Correct 7 ms 732 KB Ok
40 Correct 7 ms 652 KB Ok
41 Correct 7 ms 736 KB Ok
42 Correct 6 ms 716 KB Ok
43 Correct 6 ms 716 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Ok
2 Correct 0 ms 204 KB Ok
3 Correct 0 ms 204 KB Ok
4 Correct 0 ms 204 KB Ok
5 Correct 1 ms 204 KB Ok
6 Correct 1 ms 204 KB Ok
7 Correct 1 ms 204 KB Ok
8 Correct 1 ms 204 KB Ok
9 Correct 1 ms 204 KB Ok
10 Correct 0 ms 204 KB Ok
11 Correct 0 ms 204 KB Ok
12 Correct 0 ms 204 KB Ok
13 Correct 0 ms 204 KB Ok
14 Correct 0 ms 204 KB Ok
15 Correct 1 ms 204 KB Ok
16 Correct 1 ms 284 KB Ok
17 Correct 1 ms 204 KB Ok
18 Correct 3 ms 460 KB Ok
19 Correct 15 ms 1336 KB Ok
20 Correct 6 ms 716 KB Ok
21 Correct 17 ms 1484 KB Ok
22 Correct 9 ms 972 KB Ok
23 Correct 0 ms 204 KB Ok
24 Correct 0 ms 204 KB Ok
25 Correct 1 ms 204 KB Ok
26 Correct 1 ms 204 KB Ok
27 Correct 1 ms 204 KB Ok
28 Correct 0 ms 204 KB Ok
29 Correct 1 ms 204 KB Ok
30 Correct 1 ms 204 KB Ok
31 Correct 1 ms 204 KB Ok
32 Correct 1 ms 204 KB Ok
33 Correct 0 ms 204 KB Ok
34 Correct 3 ms 332 KB Ok
35 Correct 3 ms 332 KB Ok
36 Correct 3 ms 384 KB Ok
37 Correct 3 ms 332 KB Ok
38 Correct 2 ms 332 KB Ok
39 Correct 2 ms 332 KB Ok
40 Correct 2 ms 332 KB Ok
41 Correct 3 ms 332 KB Ok
42 Correct 3 ms 332 KB Ok
43 Correct 2 ms 332 KB Ok
44 Correct 8 ms 716 KB Ok
45 Correct 6 ms 716 KB Ok
46 Correct 6 ms 716 KB Ok
47 Correct 6 ms 716 KB Ok
48 Correct 7 ms 716 KB Ok
49 Correct 7 ms 732 KB Ok
50 Correct 7 ms 652 KB Ok
51 Correct 7 ms 736 KB Ok
52 Correct 6 ms 716 KB Ok
53 Correct 6 ms 716 KB Ok
54 Correct 97 ms 3348 KB Ok
55 Correct 115 ms 3736 KB Ok
56 Correct 108 ms 3708 KB Ok
57 Correct 91 ms 2960 KB Ok
58 Correct 108 ms 3652 KB Ok
59 Correct 97 ms 3460 KB Ok
60 Correct 90 ms 3140 KB Ok
61 Correct 82 ms 3212 KB Ok
62 Correct 114 ms 4040 KB Ok
63 Correct 100 ms 3316 KB Ok
64 Correct 121 ms 3792 KB Ok
65 Correct 108 ms 3592 KB Ok
66 Correct 93 ms 3324 KB Ok
67 Correct 95 ms 3108 KB Ok
68 Correct 107 ms 3564 KB Ok
69 Correct 212 ms 13672 KB Ok
70 Correct 216 ms 14012 KB Ok
71 Correct 224 ms 13908 KB Ok
72 Correct 235 ms 13520 KB Ok
73 Correct 216 ms 13892 KB Ok
74 Correct 232 ms 13600 KB Ok
75 Correct 200 ms 13632 KB Ok
76 Correct 220 ms 13848 KB Ok
77 Correct 207 ms 13636 KB Ok
78 Correct 226 ms 13568 KB Ok
79 Correct 210 ms 14032 KB Ok
80 Correct 206 ms 13636 KB Ok
81 Correct 227 ms 14072 KB Ok
82 Correct 234 ms 13728 KB Ok
83 Correct 206 ms 13712 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Ok
2 Correct 0 ms 204 KB Ok
3 Correct 0 ms 204 KB Ok
4 Correct 0 ms 204 KB Ok
5 Correct 1 ms 204 KB Ok
6 Correct 1 ms 204 KB Ok
7 Correct 1 ms 204 KB Ok
8 Correct 1 ms 204 KB Ok
9 Correct 1 ms 204 KB Ok
10 Correct 0 ms 204 KB Ok
11 Correct 0 ms 204 KB Ok
12 Correct 0 ms 204 KB Ok
13 Correct 0 ms 204 KB Ok
14 Correct 0 ms 204 KB Ok
15 Correct 1 ms 204 KB Ok
16 Correct 1 ms 284 KB Ok
17 Correct 1 ms 204 KB Ok
18 Correct 3 ms 460 KB Ok
19 Correct 15 ms 1336 KB Ok
20 Correct 6 ms 716 KB Ok
21 Correct 17 ms 1484 KB Ok
22 Correct 9 ms 972 KB Ok
23 Correct 0 ms 204 KB Ok
24 Correct 0 ms 204 KB Ok
25 Correct 1 ms 204 KB Ok
26 Correct 1 ms 204 KB Ok
27 Correct 1 ms 204 KB Ok
28 Correct 0 ms 204 KB Ok
29 Correct 1 ms 204 KB Ok
30 Correct 1 ms 204 KB Ok
31 Correct 1 ms 204 KB Ok
32 Correct 1 ms 204 KB Ok
33 Correct 0 ms 204 KB Ok
34 Correct 1 ms 204 KB Ok
35 Correct 0 ms 204 KB Ok
36 Correct 1 ms 204 KB Ok
37 Correct 1 ms 204 KB Ok
38 Correct 1 ms 204 KB Ok
39 Correct 174 ms 14756 KB Ok
40 Correct 148 ms 16668 KB Ok
41 Correct 278 ms 18456 KB Ok
42 Correct 210 ms 18120 KB Ok
43 Correct 138 ms 9968 KB Ok
44 Correct 242 ms 19304 KB Ok
45 Correct 3 ms 332 KB Ok
46 Correct 3 ms 332 KB Ok
47 Correct 3 ms 384 KB Ok
48 Correct 3 ms 332 KB Ok
49 Correct 2 ms 332 KB Ok
50 Correct 2 ms 332 KB Ok
51 Correct 2 ms 332 KB Ok
52 Correct 3 ms 332 KB Ok
53 Correct 3 ms 332 KB Ok
54 Correct 2 ms 332 KB Ok
55 Correct 8 ms 716 KB Ok
56 Correct 6 ms 716 KB Ok
57 Correct 6 ms 716 KB Ok
58 Correct 6 ms 716 KB Ok
59 Correct 7 ms 716 KB Ok
60 Correct 7 ms 732 KB Ok
61 Correct 7 ms 652 KB Ok
62 Correct 7 ms 736 KB Ok
63 Correct 6 ms 716 KB Ok
64 Correct 6 ms 716 KB Ok
65 Correct 97 ms 3348 KB Ok
66 Correct 115 ms 3736 KB Ok
67 Correct 108 ms 3708 KB Ok
68 Correct 91 ms 2960 KB Ok
69 Correct 108 ms 3652 KB Ok
70 Correct 97 ms 3460 KB Ok
71 Correct 90 ms 3140 KB Ok
72 Correct 82 ms 3212 KB Ok
73 Correct 114 ms 4040 KB Ok
74 Correct 100 ms 3316 KB Ok
75 Correct 121 ms 3792 KB Ok
76 Correct 108 ms 3592 KB Ok
77 Correct 93 ms 3324 KB Ok
78 Correct 95 ms 3108 KB Ok
79 Correct 107 ms 3564 KB Ok
80 Correct 212 ms 13672 KB Ok
81 Correct 216 ms 14012 KB Ok
82 Correct 224 ms 13908 KB Ok
83 Correct 235 ms 13520 KB Ok
84 Correct 216 ms 13892 KB Ok
85 Correct 232 ms 13600 KB Ok
86 Correct 200 ms 13632 KB Ok
87 Correct 220 ms 13848 KB Ok
88 Correct 207 ms 13636 KB Ok
89 Correct 226 ms 13568 KB Ok
90 Correct 210 ms 14032 KB Ok
91 Correct 206 ms 13636 KB Ok
92 Correct 227 ms 14072 KB Ok
93 Correct 234 ms 13728 KB Ok
94 Correct 206 ms 13712 KB Ok
95 Correct 272 ms 8316 KB Ok
96 Correct 385 ms 11964 KB Ok
97 Correct 353 ms 10644 KB Ok
98 Correct 273 ms 9144 KB Ok
99 Correct 298 ms 9720 KB Ok
100 Correct 343 ms 10552 KB Ok
101 Correct 353 ms 10484 KB Ok
102 Correct 335 ms 10248 KB Ok
103 Correct 323 ms 10712 KB Ok
104 Correct 397 ms 11756 KB Ok
105 Correct 347 ms 11692 KB Ok
106 Correct 325 ms 10256 KB Ok
107 Correct 375 ms 11032 KB Ok
108 Correct 376 ms 12224 KB Ok
109 Correct 333 ms 11324 KB Ok
110 Correct 934 ms 54932 KB Ok
111 Correct 995 ms 56752 KB Ok
112 Correct 952 ms 57044 KB Ok
113 Correct 954 ms 55540 KB Ok
114 Correct 1000 ms 57468 KB Ok
115 Correct 1000 ms 56764 KB Ok
116 Correct 1010 ms 57564 KB Ok
117 Correct 955 ms 55912 KB Ok
118 Correct 1002 ms 57588 KB Ok
119 Correct 1016 ms 55496 KB Ok
120 Correct 980 ms 56120 KB Ok
121 Correct 954 ms 55792 KB Ok
122 Correct 950 ms 56364 KB Ok
123 Correct 1012 ms 56812 KB Ok
124 Correct 977 ms 57296 KB Ok
125 Correct 1199 ms 38960 KB Ok