oj.uz

Submission #518700

# Submission time Handle Problem Language Result Execution time Memory
518700 2022-01-24T12:54:28 Z spike1236 Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 45292 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 = 5e5 + 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);
        reverse(all(ts));
        if(cyc) {
            r = mid - 1;
            continue;
        }
        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 7 ms 11984 KB Ok
2 Correct 7 ms 12080 KB Ok
3 Correct 7 ms 12036 KB Ok
4 Correct 7 ms 11984 KB Ok
5 Correct 6 ms 11984 KB Ok
6 Correct 10 ms 11984 KB Ok
7 Correct 7 ms 11984 KB Ok
8 Correct 8 ms 12068 KB Ok
9 Correct 9 ms 12048 KB Ok
10 Correct 10 ms 11984 KB Ok
11 Correct 7 ms 11960 KB Ok
12 Correct 7 ms 12068 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12016 KB Ok
2 Correct 6 ms 11984 KB Ok
3 Correct 7 ms 12076 KB Ok
4 Correct 7 ms 11984 KB Ok
5 Correct 6 ms 11984 KB Ok
6 Correct 14 ms 12240 KB Ok
7 Correct 45 ms 13208 KB Ok
8 Correct 20 ms 12596 KB Ok
9 Correct 44 ms 13324 KB Ok
10 Correct 26 ms 12752 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12068 KB Ok
2 Correct 8 ms 12064 KB Ok
3 Correct 8 ms 12072 KB Ok
4 Correct 7 ms 12084 KB Ok
5 Correct 7 ms 12096 KB Ok
6 Correct 431 ms 29404 KB Ok
7 Correct 396 ms 31376 KB Ok
8 Correct 831 ms 33340 KB Ok
9 Correct 494 ms 32364 KB Ok
10 Correct 262 ms 23820 KB Ok
11 Correct 480 ms 33984 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11984 KB Ok
2 Correct 7 ms 12080 KB Ok
3 Correct 7 ms 12036 KB Ok
4 Correct 7 ms 11984 KB Ok
5 Correct 6 ms 11984 KB Ok
6 Correct 10 ms 11984 KB Ok
7 Correct 7 ms 11984 KB Ok
8 Correct 8 ms 12068 KB Ok
9 Correct 9 ms 12048 KB Ok
10 Correct 10 ms 11984 KB Ok
11 Correct 7 ms 11960 KB Ok
12 Correct 7 ms 12068 KB Ok
13 Correct 7 ms 11984 KB Ok
14 Correct 6 ms 11984 KB Ok
15 Correct 7 ms 11984 KB Ok
16 Correct 7 ms 11984 KB Ok
17 Correct 6 ms 11984 KB Ok
18 Correct 7 ms 11984 KB Ok
19 Correct 6 ms 11984 KB Ok
20 Correct 6 ms 11984 KB Ok
21 Correct 7 ms 11984 KB Ok
22 Correct 7 ms 11984 KB Ok
23 Correct 8 ms 12040 KB Ok
24 Correct 12 ms 12164 KB Ok
25 Correct 12 ms 12248 KB Ok
26 Correct 14 ms 12224 KB Ok
27 Correct 11 ms 12180 KB Ok
28 Correct 10 ms 12112 KB Ok
29 Correct 13 ms 12112 KB Ok
30 Correct 11 ms 12104 KB Ok
31 Correct 13 ms 12240 KB Ok
32 Correct 11 ms 12192 KB Ok
33 Correct 10 ms 12196 KB Ok
34 Correct 19 ms 12452 KB Ok
35 Correct 19 ms 12428 KB Ok
36 Correct 19 ms 12496 KB Ok
37 Correct 17 ms 12508 KB Ok
38 Correct 19 ms 12500 KB Ok
39 Correct 17 ms 12444 KB Ok
40 Correct 19 ms 12440 KB Ok
41 Correct 18 ms 12468 KB Ok
42 Correct 22 ms 12496 KB Ok
43 Correct 20 ms 12540 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11984 KB Ok
2 Correct 7 ms 12080 KB Ok
3 Correct 7 ms 12036 KB Ok
4 Correct 7 ms 11984 KB Ok
5 Correct 6 ms 11984 KB Ok
6 Correct 10 ms 11984 KB Ok
7 Correct 7 ms 11984 KB Ok
8 Correct 8 ms 12068 KB Ok
9 Correct 9 ms 12048 KB Ok
10 Correct 10 ms 11984 KB Ok
11 Correct 7 ms 11960 KB Ok
12 Correct 7 ms 12068 KB Ok
13 Correct 7 ms 12016 KB Ok
14 Correct 6 ms 11984 KB Ok
15 Correct 7 ms 12076 KB Ok
16 Correct 7 ms 11984 KB Ok
17 Correct 6 ms 11984 KB Ok
18 Correct 14 ms 12240 KB Ok
19 Correct 45 ms 13208 KB Ok
20 Correct 20 ms 12596 KB Ok
21 Correct 44 ms 13324 KB Ok
22 Correct 26 ms 12752 KB Ok
23 Correct 7 ms 11984 KB Ok
24 Correct 6 ms 11984 KB Ok
25 Correct 7 ms 11984 KB Ok
26 Correct 7 ms 11984 KB Ok
27 Correct 6 ms 11984 KB Ok
28 Correct 7 ms 11984 KB Ok
29 Correct 6 ms 11984 KB Ok
30 Correct 6 ms 11984 KB Ok
31 Correct 7 ms 11984 KB Ok
32 Correct 7 ms 11984 KB Ok
33 Correct 8 ms 12040 KB Ok
34 Correct 12 ms 12164 KB Ok
35 Correct 12 ms 12248 KB Ok
36 Correct 14 ms 12224 KB Ok
37 Correct 11 ms 12180 KB Ok
38 Correct 10 ms 12112 KB Ok
39 Correct 13 ms 12112 KB Ok
40 Correct 11 ms 12104 KB Ok
41 Correct 13 ms 12240 KB Ok
42 Correct 11 ms 12192 KB Ok
43 Correct 10 ms 12196 KB Ok
44 Correct 19 ms 12452 KB Ok
45 Correct 19 ms 12428 KB Ok
46 Correct 19 ms 12496 KB Ok
47 Correct 17 ms 12508 KB Ok
48 Correct 19 ms 12500 KB Ok
49 Correct 17 ms 12444 KB Ok
50 Correct 19 ms 12440 KB Ok
51 Correct 18 ms 12468 KB Ok
52 Correct 22 ms 12496 KB Ok
53 Correct 20 ms 12540 KB Ok
54 Correct 259 ms 17852 KB Ok
55 Correct 344 ms 18244 KB Ok
56 Correct 332 ms 18196 KB Ok
57 Correct 234 ms 17160 KB Ok
58 Correct 265 ms 18084 KB Ok
59 Correct 244 ms 17752 KB Ok
60 Correct 214 ms 17292 KB Ok
61 Correct 207 ms 17572 KB Ok
62 Correct 300 ms 18500 KB Ok
63 Correct 246 ms 17612 KB Ok
64 Correct 334 ms 18216 KB Ok
65 Correct 264 ms 18176 KB Ok
66 Correct 246 ms 17804 KB Ok
67 Correct 237 ms 17632 KB Ok
68 Correct 255 ms 18052 KB Ok
69 Correct 793 ms 26816 KB Ok
70 Correct 981 ms 27292 KB Ok
71 Correct 826 ms 26880 KB Ok
72 Correct 718 ms 26692 KB Ok
73 Correct 944 ms 27116 KB Ok
74 Correct 705 ms 26692 KB Ok
75 Correct 811 ms 26828 KB Ok
76 Correct 943 ms 27004 KB Ok
77 Correct 674 ms 26728 KB Ok
78 Correct 1038 ms 26684 KB Ok
79 Correct 1000 ms 27156 KB Ok
80 Correct 683 ms 26832 KB Ok
81 Correct 912 ms 27200 KB Ok
82 Correct 743 ms 26956 KB Ok
83 Correct 676 ms 26972 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11984 KB Ok
2 Correct 7 ms 12080 KB Ok
3 Correct 7 ms 12036 KB Ok
4 Correct 7 ms 11984 KB Ok
5 Correct 6 ms 11984 KB Ok
6 Correct 10 ms 11984 KB Ok
7 Correct 7 ms 11984 KB Ok
8 Correct 8 ms 12068 KB Ok
9 Correct 9 ms 12048 KB Ok
10 Correct 10 ms 11984 KB Ok
11 Correct 7 ms 11960 KB Ok
12 Correct 7 ms 12068 KB Ok
13 Correct 7 ms 12016 KB Ok
14 Correct 6 ms 11984 KB Ok
15 Correct 7 ms 12076 KB Ok
16 Correct 7 ms 11984 KB Ok
17 Correct 6 ms 11984 KB Ok
18 Correct 14 ms 12240 KB Ok
19 Correct 45 ms 13208 KB Ok
20 Correct 20 ms 12596 KB Ok
21 Correct 44 ms 13324 KB Ok
22 Correct 26 ms 12752 KB Ok
23 Correct 7 ms 11984 KB Ok
24 Correct 6 ms 11984 KB Ok
25 Correct 7 ms 11984 KB Ok
26 Correct 7 ms 11984 KB Ok
27 Correct 6 ms 11984 KB Ok
28 Correct 7 ms 11984 KB Ok
29 Correct 6 ms 11984 KB Ok
30 Correct 6 ms 11984 KB Ok
31 Correct 7 ms 11984 KB Ok
32 Correct 7 ms 11984 KB Ok
33 Correct 8 ms 12040 KB Ok
34 Correct 7 ms 12068 KB Ok
35 Correct 8 ms 12064 KB Ok
36 Correct 8 ms 12072 KB Ok
37 Correct 7 ms 12084 KB Ok
38 Correct 7 ms 12096 KB Ok
39 Correct 431 ms 29404 KB Ok
40 Correct 396 ms 31376 KB Ok
41 Correct 831 ms 33340 KB Ok
42 Correct 494 ms 32364 KB Ok
43 Correct 262 ms 23820 KB Ok
44 Correct 480 ms 33984 KB Ok
45 Correct 12 ms 12164 KB Ok
46 Correct 12 ms 12248 KB Ok
47 Correct 14 ms 12224 KB Ok
48 Correct 11 ms 12180 KB Ok
49 Correct 10 ms 12112 KB Ok
50 Correct 13 ms 12112 KB Ok
51 Correct 11 ms 12104 KB Ok
52 Correct 13 ms 12240 KB Ok
53 Correct 11 ms 12192 KB Ok
54 Correct 10 ms 12196 KB Ok
55 Correct 19 ms 12452 KB Ok
56 Correct 19 ms 12428 KB Ok
57 Correct 19 ms 12496 KB Ok
58 Correct 17 ms 12508 KB Ok
59 Correct 19 ms 12500 KB Ok
60 Correct 17 ms 12444 KB Ok
61 Correct 19 ms 12440 KB Ok
62 Correct 18 ms 12468 KB Ok
63 Correct 22 ms 12496 KB Ok
64 Correct 20 ms 12540 KB Ok
65 Correct 259 ms 17852 KB Ok
66 Correct 344 ms 18244 KB Ok
67 Correct 332 ms 18196 KB Ok
68 Correct 234 ms 17160 KB Ok
69 Correct 265 ms 18084 KB Ok
70 Correct 244 ms 17752 KB Ok
71 Correct 214 ms 17292 KB Ok
72 Correct 207 ms 17572 KB Ok
73 Correct 300 ms 18500 KB Ok
74 Correct 246 ms 17612 KB Ok
75 Correct 334 ms 18216 KB Ok
76 Correct 264 ms 18176 KB Ok
77 Correct 246 ms 17804 KB Ok
78 Correct 237 ms 17632 KB Ok
79 Correct 255 ms 18052 KB Ok
80 Correct 793 ms 26816 KB Ok
81 Correct 981 ms 27292 KB Ok
82 Correct 826 ms 26880 KB Ok
83 Correct 718 ms 26692 KB Ok
84 Correct 944 ms 27116 KB Ok
85 Correct 705 ms 26692 KB Ok
86 Correct 811 ms 26828 KB Ok
87 Correct 943 ms 27004 KB Ok
88 Correct 674 ms 26728 KB Ok
89 Correct 1038 ms 26684 KB Ok
90 Correct 1000 ms 27156 KB Ok
91 Correct 683 ms 26832 KB Ok
92 Correct 912 ms 27200 KB Ok
93 Correct 743 ms 26956 KB Ok
94 Correct 676 ms 26972 KB Ok
95 Correct 744 ms 27492 KB Ok
96 Correct 1000 ms 34984 KB Ok
97 Correct 965 ms 31296 KB Ok
98 Correct 663 ms 30464 KB Ok
99 Correct 836 ms 30260 KB Ok
100 Correct 874 ms 30532 KB Ok
101 Correct 926 ms 32588 KB Ok
102 Correct 877 ms 31032 KB Ok
103 Correct 833 ms 32404 KB Ok
104 Correct 1205 ms 33832 KB Ok
105 Correct 1018 ms 34416 KB Ok
106 Correct 936 ms 33312 KB Ok
107 Correct 969 ms 33240 KB Ok
108 Correct 1146 ms 34516 KB Ok
109 Correct 1014 ms 34804 KB Ok
110 Execution timed out 2083 ms 45292 KB Time limit exceeded
111 Halted 0 ms 0 KB -