oj.uz

Submission #161615

# Submission time Handle Problem Language Result Execution time Memory
161615 2019-11-03T10:01:00 Z srvlt Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 45408 KB 
//#pragma GCC target ("avx2,sse2")
//#pragma GCC optimization ("Ofast")
//#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long
#define db long double
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define fi first
#define se second
#define mp make_pair
#define up_b upper_bound
#define low_b lower_bound
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
//#define endl "\n"

#define left fsdkfsdfsdfd
#define sum dfsdfsdfsdf
#define assign sdkfskdfkk

//#define int long long

using namespace std;

void dout() {
    cerr << endl;
}
template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;

int bit(signed x) {
    return __builtin_popcount(x);
}
int bit(ll x) {
    return __builtin_popcountll(x);
}

const int N = 4e5 + 123;
int n, m, k, used[N], p[N], a[N];
bool cycle;
vector <int> topsort;

void cleanup() {
    k = 0;
    cycle = false;
    topsort = {};
    for (int i = 0; i < N; i++) {
        used[i] = 0;
        p[i] = 0;
        a[i] = 0;
    }
}

void dfs(int v, bool flag) {
    used[v] = 1;
    if (v - n >= 0) {
        if (used[v - n] == 1) {
            cycle = true;
            return;
        }
        if (used[v - n] == 0) {
            dfs(v - n, flag);
        }
    }
    if (v + m <= k) {
        if (used[v + m] == 1) {
            cycle = true;
            return;
        }
        if (used[v + m] == 0) {
            dfs(v + m, flag);
        }
    }
    used[v] = 2;
    if (flag) {
        topsort.pb(v);
    }
}

bool check() {
    if (k == 0) {
        return true;
    }
    cycle = false;
    for (int i = 0; i <= k; i++) {
        if (used[i] == 0) {
            dfs(i, false);
        }
    }
    for (int i = 0; i <= k; i++) {
        used[i] = 0;
    }
    return !cycle;
}

void construct() {
    for (int i = 0; i <= k; i++) {
        if (used[i] == 0) {
            dfs(i, true);
        }
    }
    reverse(topsort.begin(), topsort.end());
    for (int i = 0; i <= k; i++) {
        p[topsort[i]] = i;
    }
    bool zero = false;
    for (int i = 1; i <= k; i++) {
        a[i] = p[i] - p[i - 1];
        if (a[i] == 0) {
            zero = true;
        }
    }
    cout << k << endl;
    for (int i = 1; i <= k; i++) {
        if (zero) {
            a[i]++;
        }
        cout << a[i] << " ";
    }
    cout << endl;
}

void solve(int tc) {
    // check for (int i = 0; i < n; j++)
    cin >> n >> m;
    int l = -1, r = 2 * max(n, m) + 7;
    while (l < r - 1) {
        int mid = l + r >> 1;
        k = mid;
        if (check()) {
            l = mid;
        }   else {
            r = mid;
        }
    }
    k = l;
    construct();
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int tc = 1;
    cin >> tc;
    for (int i = 0; i < tc; i++) {
        solve(i);
        cleanup();
    }
}

Compilation message

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4984 KB Ok
2 Correct 15 ms 4984 KB Ok
3 Correct 14 ms 4984 KB Ok
4 Correct 15 ms 4984 KB Ok
5 Correct 15 ms 5116 KB Ok
6 Correct 14 ms 4988 KB Ok
7 Correct 16 ms 5084 KB Ok
8 Correct 14 ms 5112 KB Ok
9 Correct 15 ms 5112 KB Ok
10 Correct 15 ms 5112 KB Ok
11 Correct 15 ms 5112 KB Ok
12 Correct 15 ms 4988 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5112 KB Ok
2 Correct 14 ms 4984 KB Ok
3 Correct 14 ms 4984 KB Ok
4 Correct 14 ms 5112 KB Ok
5 Correct 14 ms 4984 KB Ok
6 Correct 18 ms 5240 KB Ok
7 Correct 32 ms 5880 KB Ok
8 Correct 22 ms 5368 KB Ok
9 Correct 37 ms 6008 KB Ok
10 Correct 27 ms 5596 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5112 KB Ok
2 Correct 14 ms 5112 KB Ok
3 Correct 14 ms 4984 KB Ok
4 Correct 15 ms 4984 KB Ok
5 Correct 14 ms 4984 KB Ok
6 Correct 15 ms 5084 KB Ok
7 Correct 14 ms 4988 KB Ok
8 Correct 15 ms 4984 KB Ok
9 Correct 15 ms 4984 KB Ok
10 Correct 15 ms 5112 KB Ok
11 Correct 14 ms 5112 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5112 KB Ok
2 Correct 14 ms 4984 KB Ok
3 Correct 14 ms 5112 KB Ok
4 Correct 14 ms 5112 KB Ok
5 Correct 14 ms 5112 KB Ok
6 Correct 262 ms 14144 KB Ok
7 Correct 208 ms 14404 KB Ok
8 Correct 398 ms 16496 KB Ok
9 Correct 328 ms 16880 KB Ok
10 Correct 196 ms 11408 KB Ok
11 Correct 359 ms 17008 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4984 KB Ok
2 Correct 15 ms 4984 KB Ok
3 Correct 14 ms 4984 KB Ok
4 Correct 15 ms 4984 KB Ok
5 Correct 15 ms 5116 KB Ok
6 Correct 14 ms 4988 KB Ok
7 Correct 16 ms 5084 KB Ok
8 Correct 14 ms 5112 KB Ok
9 Correct 15 ms 5112 KB Ok
10 Correct 15 ms 5112 KB Ok
11 Correct 15 ms 5112 KB Ok
12 Correct 15 ms 4988 KB Ok
13 Correct 9 ms 5112 KB Ok
14 Correct 14 ms 5112 KB Ok
15 Correct 14 ms 4984 KB Ok
16 Correct 15 ms 4984 KB Ok
17 Correct 14 ms 4984 KB Ok
18 Correct 15 ms 5084 KB Ok
19 Correct 14 ms 4988 KB Ok
20 Correct 15 ms 4984 KB Ok
21 Correct 15 ms 4984 KB Ok
22 Correct 15 ms 5112 KB Ok
23 Correct 14 ms 5112 KB Ok
24 Correct 17 ms 5112 KB Ok
25 Correct 17 ms 5112 KB Ok
26 Correct 17 ms 5128 KB Ok
27 Correct 18 ms 5112 KB Ok
28 Correct 16 ms 5112 KB Ok
29 Correct 17 ms 5112 KB Ok
30 Correct 16 ms 5112 KB Ok
31 Correct 21 ms 5112 KB Ok
32 Correct 17 ms 5112 KB Ok
33 Correct 17 ms 5112 KB Ok
34 Correct 24 ms 5372 KB Ok
35 Correct 23 ms 5368 KB Ok
36 Correct 22 ms 5368 KB Ok
37 Correct 22 ms 5368 KB Ok
38 Correct 22 ms 5368 KB Ok
39 Correct 22 ms 5368 KB Ok
40 Correct 24 ms 5372 KB Ok
41 Correct 22 ms 5368 KB Ok
42 Correct 23 ms 5624 KB Ok
43 Correct 23 ms 5368 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4984 KB Ok
2 Correct 15 ms 4984 KB Ok
3 Correct 14 ms 4984 KB Ok
4 Correct 15 ms 4984 KB Ok
5 Correct 15 ms 5116 KB Ok
6 Correct 14 ms 4988 KB Ok
7 Correct 16 ms 5084 KB Ok
8 Correct 14 ms 5112 KB Ok
9 Correct 15 ms 5112 KB Ok
10 Correct 15 ms 5112 KB Ok
11 Correct 15 ms 5112 KB Ok
12 Correct 15 ms 4988 KB Ok
13 Correct 16 ms 5112 KB Ok
14 Correct 14 ms 4984 KB Ok
15 Correct 14 ms 4984 KB Ok
16 Correct 14 ms 5112 KB Ok
17 Correct 14 ms 4984 KB Ok
18 Correct 18 ms 5240 KB Ok
19 Correct 32 ms 5880 KB Ok
20 Correct 22 ms 5368 KB Ok
21 Correct 37 ms 6008 KB Ok
22 Correct 27 ms 5596 KB Ok
23 Correct 9 ms 5112 KB Ok
24 Correct 14 ms 5112 KB Ok
25 Correct 14 ms 4984 KB Ok
26 Correct 15 ms 4984 KB Ok
27 Correct 14 ms 4984 KB Ok
28 Correct 15 ms 5084 KB Ok
29 Correct 14 ms 4988 KB Ok
30 Correct 15 ms 4984 KB Ok
31 Correct 15 ms 4984 KB Ok
32 Correct 15 ms 5112 KB Ok
33 Correct 14 ms 5112 KB Ok
34 Correct 17 ms 5112 KB Ok
35 Correct 17 ms 5112 KB Ok
36 Correct 17 ms 5128 KB Ok
37 Correct 18 ms 5112 KB Ok
38 Correct 16 ms 5112 KB Ok
39 Correct 17 ms 5112 KB Ok
40 Correct 16 ms 5112 KB Ok
41 Correct 21 ms 5112 KB Ok
42 Correct 17 ms 5112 KB Ok
43 Correct 17 ms 5112 KB Ok
44 Correct 24 ms 5372 KB Ok
45 Correct 23 ms 5368 KB Ok
46 Correct 22 ms 5368 KB Ok
47 Correct 22 ms 5368 KB Ok
48 Correct 22 ms 5368 KB Ok
49 Correct 22 ms 5368 KB Ok
50 Correct 24 ms 5372 KB Ok
51 Correct 22 ms 5368 KB Ok
52 Correct 23 ms 5624 KB Ok
53 Correct 23 ms 5368 KB Ok
54 Correct 162 ms 7848 KB Ok
55 Correct 180 ms 8304 KB Ok
56 Correct 177 ms 8052 KB Ok
57 Correct 130 ms 7400 KB Ok
58 Correct 164 ms 7984 KB Ok
59 Correct 160 ms 7924 KB Ok
60 Correct 145 ms 7540 KB Ok
61 Correct 132 ms 7540 KB Ok
62 Correct 195 ms 8480 KB Ok
63 Correct 148 ms 7668 KB Ok
64 Correct 188 ms 8180 KB Ok
65 Correct 163 ms 8160 KB Ok
66 Correct 147 ms 7796 KB Ok
67 Correct 131 ms 7412 KB Ok
68 Correct 162 ms 8052 KB Ok
69 Correct 375 ms 14836 KB Ok
70 Correct 388 ms 15400 KB Ok
71 Correct 381 ms 15064 KB Ok
72 Correct 364 ms 14836 KB Ok
73 Correct 456 ms 15348 KB Ok
74 Correct 363 ms 14748 KB Ok
75 Correct 360 ms 14708 KB Ok
76 Correct 390 ms 14964 KB Ok
77 Correct 361 ms 14724 KB Ok
78 Correct 413 ms 14904 KB Ok
79 Correct 393 ms 15220 KB Ok
80 Correct 364 ms 14836 KB Ok
81 Correct 366 ms 15240 KB Ok
82 Correct 371 ms 15048 KB Ok
83 Correct 373 ms 15028 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4984 KB Ok
2 Correct 15 ms 4984 KB Ok
3 Correct 14 ms 4984 KB Ok
4 Correct 15 ms 4984 KB Ok
5 Correct 15 ms 5116 KB Ok
6 Correct 14 ms 4988 KB Ok
7 Correct 16 ms 5084 KB Ok
8 Correct 14 ms 5112 KB Ok
9 Correct 15 ms 5112 KB Ok
10 Correct 15 ms 5112 KB Ok
11 Correct 15 ms 5112 KB Ok
12 Correct 15 ms 4988 KB Ok
13 Correct 16 ms 5112 KB Ok
14 Correct 14 ms 4984 KB Ok
15 Correct 14 ms 4984 KB Ok
16 Correct 14 ms 5112 KB Ok
17 Correct 14 ms 4984 KB Ok
18 Correct 18 ms 5240 KB Ok
19 Correct 32 ms 5880 KB Ok
20 Correct 22 ms 5368 KB Ok
21 Correct 37 ms 6008 KB Ok
22 Correct 27 ms 5596 KB Ok
23 Correct 9 ms 5112 KB Ok
24 Correct 14 ms 5112 KB Ok
25 Correct 14 ms 4984 KB Ok
26 Correct 15 ms 4984 KB Ok
27 Correct 14 ms 4984 KB Ok
28 Correct 15 ms 5084 KB Ok
29 Correct 14 ms 4988 KB Ok
30 Correct 15 ms 4984 KB Ok
31 Correct 15 ms 4984 KB Ok
32 Correct 15 ms 5112 KB Ok
33 Correct 14 ms 5112 KB Ok
34 Correct 14 ms 5112 KB Ok
35 Correct 14 ms 4984 KB Ok
36 Correct 14 ms 5112 KB Ok
37 Correct 14 ms 5112 KB Ok
38 Correct 14 ms 5112 KB Ok
39 Correct 262 ms 14144 KB Ok
40 Correct 208 ms 14404 KB Ok
41 Correct 398 ms 16496 KB Ok
42 Correct 328 ms 16880 KB Ok
43 Correct 196 ms 11408 KB Ok
44 Correct 359 ms 17008 KB Ok
45 Correct 17 ms 5112 KB Ok
46 Correct 17 ms 5112 KB Ok
47 Correct 17 ms 5128 KB Ok
48 Correct 18 ms 5112 KB Ok
49 Correct 16 ms 5112 KB Ok
50 Correct 17 ms 5112 KB Ok
51 Correct 16 ms 5112 KB Ok
52 Correct 21 ms 5112 KB Ok
53 Correct 17 ms 5112 KB Ok
54 Correct 17 ms 5112 KB Ok
55 Correct 24 ms 5372 KB Ok
56 Correct 23 ms 5368 KB Ok
57 Correct 22 ms 5368 KB Ok
58 Correct 22 ms 5368 KB Ok
59 Correct 22 ms 5368 KB Ok
60 Correct 22 ms 5368 KB Ok
61 Correct 24 ms 5372 KB Ok
62 Correct 22 ms 5368 KB Ok
63 Correct 23 ms 5624 KB Ok
64 Correct 23 ms 5368 KB Ok
65 Correct 162 ms 7848 KB Ok
66 Correct 180 ms 8304 KB Ok
67 Correct 177 ms 8052 KB Ok
68 Correct 130 ms 7400 KB Ok
69 Correct 164 ms 7984 KB Ok
70 Correct 160 ms 7924 KB Ok
71 Correct 145 ms 7540 KB Ok
72 Correct 132 ms 7540 KB Ok
73 Correct 195 ms 8480 KB Ok
74 Correct 148 ms 7668 KB Ok
75 Correct 188 ms 8180 KB Ok
76 Correct 163 ms 8160 KB Ok
77 Correct 147 ms 7796 KB Ok
78 Correct 131 ms 7412 KB Ok
79 Correct 162 ms 8052 KB Ok
80 Correct 375 ms 14836 KB Ok
81 Correct 388 ms 15400 KB Ok
82 Correct 381 ms 15064 KB Ok
83 Correct 364 ms 14836 KB Ok
84 Correct 456 ms 15348 KB Ok
85 Correct 363 ms 14748 KB Ok
86 Correct 360 ms 14708 KB Ok
87 Correct 390 ms 14964 KB Ok
88 Correct 361 ms 14724 KB Ok
89 Correct 413 ms 14904 KB Ok
90 Correct 393 ms 15220 KB Ok
91 Correct 364 ms 14836 KB Ok
92 Correct 366 ms 15240 KB Ok
93 Correct 371 ms 15048 KB Ok
94 Correct 373 ms 15028 KB Ok
95 Correct 379 ms 12016 KB Ok
96 Correct 590 ms 15236 KB Ok
97 Correct 579 ms 14040 KB Ok
98 Correct 399 ms 12428 KB Ok
99 Correct 458 ms 13160 KB Ok
100 Correct 516 ms 13928 KB Ok
101 Correct 599 ms 13744 KB Ok
102 Correct 489 ms 13832 KB Ok
103 Correct 508 ms 13932 KB Ok
104 Correct 573 ms 15036 KB Ok
105 Correct 601 ms 14844 KB Ok
106 Correct 512 ms 13416 KB Ok
107 Correct 564 ms 14184 KB Ok
108 Correct 646 ms 15428 KB Ok
109 Correct 536 ms 14312 KB Ok
110 Correct 1922 ms 45408 KB Ok
111 Execution timed out 2061 ms 41688 KB Time limit exceeded
112 Halted 0 ms 0 KB -