Submission #161634

# Submission time Handle Problem Language Result Execution time Memory
161634 2019-11-03T11:18:53 Z srvlt Nice sequence (IZhO18_sequence) C++14
76 / 100
2000 ms 45300 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() {
    cycle = false;
    topsort = {};
    for (int i = 0; i <= k; i++) {
        used[i] = p[i] = a[i] = 0;
    }
    k = 0;
}
 
void dfs(int v) {
    used[v] = 1;
    if (v - n >= 0) {
        if (used[v - n] == 1) {
            cycle = true;
            return;
        }
        if (used[v - n] == 0) {
            dfs(v - n);
        }
    }
    if (v + m <= k) {
        if (used[v + m] == 1) {
            cycle = true;
            return;
        }
        if (used[v + m] == 0) {
            dfs(v + m);
        }
    }
    used[v] = 2;
}
 
void get(int v) {
    used[v] = 1;
    if (v - n >= 0) {
        if (!used[v - n]) {
            get(v - n);
        }
    }
    if (v + m <= k) {
        if (!used[v + m]) {
            get(v + m);
        }
    }
    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);
        }
    }
    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) {
            get(i);
        }
    }
    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 = min(n, m) - 2, 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:151:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Ok
2 Correct 2 ms 376 KB Ok
3 Correct 2 ms 376 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 3 ms 376 KB Ok
7 Correct 2 ms 376 KB Ok
8 Correct 2 ms 504 KB Ok
9 Correct 2 ms 376 KB Ok
10 Correct 2 ms 376 KB Ok
11 Correct 2 ms 376 KB Ok
12 Correct 2 ms 276 KB Ok
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Ok
2 Correct 2 ms 376 KB Ok
3 Correct 2 ms 420 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 380 KB Ok
6 Correct 5 ms 584 KB Ok
7 Correct 19 ms 1272 KB Ok
8 Correct 9 ms 760 KB Ok
9 Correct 25 ms 1448 KB Ok
10 Correct 12 ms 888 KB Ok
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Ok
2 Correct 2 ms 416 KB Ok
3 Correct 2 ms 376 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 2 ms 376 KB Ok
7 Correct 2 ms 376 KB Ok
8 Correct 2 ms 376 KB Ok
9 Correct 2 ms 376 KB Ok
10 Correct 2 ms 376 KB Ok
11 Correct 2 ms 376 KB Ok
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Ok
2 Correct 2 ms 376 KB Ok
3 Correct 2 ms 376 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 231 ms 11356 KB Ok
7 Correct 174 ms 11948 KB Ok
8 Correct 358 ms 14176 KB Ok
9 Correct 281 ms 14208 KB Ok
10 Correct 180 ms 8016 KB Ok
11 Correct 314 ms 14576 KB Ok
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Ok
2 Correct 2 ms 376 KB Ok
3 Correct 2 ms 376 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 3 ms 376 KB Ok
7 Correct 2 ms 376 KB Ok
8 Correct 2 ms 504 KB Ok
9 Correct 2 ms 376 KB Ok
10 Correct 2 ms 376 KB Ok
11 Correct 2 ms 376 KB Ok
12 Correct 2 ms 276 KB Ok
13 Correct 2 ms 376 KB Ok
14 Correct 2 ms 416 KB Ok
15 Correct 2 ms 376 KB Ok
16 Correct 2 ms 376 KB Ok
17 Correct 2 ms 376 KB Ok
18 Correct 2 ms 376 KB Ok
19 Correct 2 ms 376 KB Ok
20 Correct 2 ms 376 KB Ok
21 Correct 2 ms 376 KB Ok
22 Correct 2 ms 376 KB Ok
23 Correct 2 ms 376 KB Ok
24 Correct 5 ms 504 KB Ok
25 Correct 5 ms 504 KB Ok
26 Correct 6 ms 504 KB Ok
27 Correct 5 ms 504 KB Ok
28 Correct 4 ms 504 KB Ok
29 Correct 5 ms 504 KB Ok
30 Correct 4 ms 504 KB Ok
31 Correct 6 ms 504 KB Ok
32 Correct 5 ms 504 KB Ok
33 Correct 5 ms 504 KB Ok
34 Correct 9 ms 632 KB Ok
35 Correct 10 ms 760 KB Ok
36 Correct 9 ms 760 KB Ok
37 Correct 10 ms 760 KB Ok
38 Correct 9 ms 632 KB Ok
39 Correct 9 ms 760 KB Ok
40 Correct 10 ms 760 KB Ok
41 Correct 10 ms 632 KB Ok
42 Correct 10 ms 760 KB Ok
43 Correct 10 ms 760 KB Ok
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Ok
2 Correct 2 ms 376 KB Ok
3 Correct 2 ms 376 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 3 ms 376 KB Ok
7 Correct 2 ms 376 KB Ok
8 Correct 2 ms 504 KB Ok
9 Correct 2 ms 376 KB Ok
10 Correct 2 ms 376 KB Ok
11 Correct 2 ms 376 KB Ok
12 Correct 2 ms 276 KB Ok
13 Correct 2 ms 376 KB Ok
14 Correct 2 ms 376 KB Ok
15 Correct 2 ms 420 KB Ok
16 Correct 2 ms 376 KB Ok
17 Correct 2 ms 380 KB Ok
18 Correct 5 ms 584 KB Ok
19 Correct 19 ms 1272 KB Ok
20 Correct 9 ms 760 KB Ok
21 Correct 25 ms 1448 KB Ok
22 Correct 12 ms 888 KB Ok
23 Correct 2 ms 376 KB Ok
24 Correct 2 ms 416 KB Ok
25 Correct 2 ms 376 KB Ok
26 Correct 2 ms 376 KB Ok
27 Correct 2 ms 376 KB Ok
28 Correct 2 ms 376 KB Ok
29 Correct 2 ms 376 KB Ok
30 Correct 2 ms 376 KB Ok
31 Correct 2 ms 376 KB Ok
32 Correct 2 ms 376 KB Ok
33 Correct 2 ms 376 KB Ok
34 Correct 5 ms 504 KB Ok
35 Correct 5 ms 504 KB Ok
36 Correct 6 ms 504 KB Ok
37 Correct 5 ms 504 KB Ok
38 Correct 4 ms 504 KB Ok
39 Correct 5 ms 504 KB Ok
40 Correct 4 ms 504 KB Ok
41 Correct 6 ms 504 KB Ok
42 Correct 5 ms 504 KB Ok
43 Correct 5 ms 504 KB Ok
44 Correct 9 ms 632 KB Ok
45 Correct 10 ms 760 KB Ok
46 Correct 9 ms 760 KB Ok
47 Correct 10 ms 760 KB Ok
48 Correct 9 ms 632 KB Ok
49 Correct 9 ms 760 KB Ok
50 Correct 10 ms 760 KB Ok
51 Correct 10 ms 632 KB Ok
52 Correct 10 ms 760 KB Ok
53 Correct 10 ms 760 KB Ok
54 Correct 134 ms 4136 KB Ok
55 Correct 142 ms 4596 KB Ok
56 Correct 139 ms 4468 KB Ok
57 Correct 106 ms 3628 KB Ok
58 Correct 140 ms 4480 KB Ok
59 Correct 130 ms 4212 KB Ok
60 Correct 113 ms 3828 KB Ok
61 Correct 109 ms 3952 KB Ok
62 Correct 170 ms 4852 KB Ok
63 Correct 119 ms 4084 KB Ok
64 Correct 152 ms 4588 KB Ok
65 Correct 135 ms 4340 KB Ok
66 Correct 124 ms 4084 KB Ok
67 Correct 112 ms 3828 KB Ok
68 Correct 129 ms 4312 KB Ok
69 Correct 329 ms 11508 KB Ok
70 Correct 342 ms 11716 KB Ok
71 Correct 317 ms 11508 KB Ok
72 Correct 332 ms 11252 KB Ok
73 Correct 329 ms 11636 KB Ok
74 Correct 333 ms 11252 KB Ok
75 Correct 324 ms 11276 KB Ok
76 Correct 351 ms 11516 KB Ok
77 Correct 320 ms 11252 KB Ok
78 Correct 364 ms 11384 KB Ok
79 Correct 342 ms 11760 KB Ok
80 Correct 321 ms 11404 KB Ok
81 Correct 325 ms 11636 KB Ok
82 Correct 329 ms 11380 KB Ok
83 Correct 345 ms 11588 KB Ok
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Ok
2 Correct 2 ms 376 KB Ok
3 Correct 2 ms 376 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 3 ms 376 KB Ok
7 Correct 2 ms 376 KB Ok
8 Correct 2 ms 504 KB Ok
9 Correct 2 ms 376 KB Ok
10 Correct 2 ms 376 KB Ok
11 Correct 2 ms 376 KB Ok
12 Correct 2 ms 276 KB Ok
13 Correct 2 ms 376 KB Ok
14 Correct 2 ms 376 KB Ok
15 Correct 2 ms 420 KB Ok
16 Correct 2 ms 376 KB Ok
17 Correct 2 ms 380 KB Ok
18 Correct 5 ms 584 KB Ok
19 Correct 19 ms 1272 KB Ok
20 Correct 9 ms 760 KB Ok
21 Correct 25 ms 1448 KB Ok
22 Correct 12 ms 888 KB Ok
23 Correct 2 ms 376 KB Ok
24 Correct 2 ms 416 KB Ok
25 Correct 2 ms 376 KB Ok
26 Correct 2 ms 376 KB Ok
27 Correct 2 ms 376 KB Ok
28 Correct 2 ms 376 KB Ok
29 Correct 2 ms 376 KB Ok
30 Correct 2 ms 376 KB Ok
31 Correct 2 ms 376 KB Ok
32 Correct 2 ms 376 KB Ok
33 Correct 2 ms 376 KB Ok
34 Correct 2 ms 376 KB Ok
35 Correct 2 ms 376 KB Ok
36 Correct 2 ms 376 KB Ok
37 Correct 2 ms 376 KB Ok
38 Correct 2 ms 376 KB Ok
39 Correct 231 ms 11356 KB Ok
40 Correct 174 ms 11948 KB Ok
41 Correct 358 ms 14176 KB Ok
42 Correct 281 ms 14208 KB Ok
43 Correct 180 ms 8016 KB Ok
44 Correct 314 ms 14576 KB Ok
45 Correct 5 ms 504 KB Ok
46 Correct 5 ms 504 KB Ok
47 Correct 6 ms 504 KB Ok
48 Correct 5 ms 504 KB Ok
49 Correct 4 ms 504 KB Ok
50 Correct 5 ms 504 KB Ok
51 Correct 4 ms 504 KB Ok
52 Correct 6 ms 504 KB Ok
53 Correct 5 ms 504 KB Ok
54 Correct 5 ms 504 KB Ok
55 Correct 9 ms 632 KB Ok
56 Correct 10 ms 760 KB Ok
57 Correct 9 ms 760 KB Ok
58 Correct 10 ms 760 KB Ok
59 Correct 9 ms 632 KB Ok
60 Correct 9 ms 760 KB Ok
61 Correct 10 ms 760 KB Ok
62 Correct 10 ms 632 KB Ok
63 Correct 10 ms 760 KB Ok
64 Correct 10 ms 760 KB Ok
65 Correct 134 ms 4136 KB Ok
66 Correct 142 ms 4596 KB Ok
67 Correct 139 ms 4468 KB Ok
68 Correct 106 ms 3628 KB Ok
69 Correct 140 ms 4480 KB Ok
70 Correct 130 ms 4212 KB Ok
71 Correct 113 ms 3828 KB Ok
72 Correct 109 ms 3952 KB Ok
73 Correct 170 ms 4852 KB Ok
74 Correct 119 ms 4084 KB Ok
75 Correct 152 ms 4588 KB Ok
76 Correct 135 ms 4340 KB Ok
77 Correct 124 ms 4084 KB Ok
78 Correct 112 ms 3828 KB Ok
79 Correct 129 ms 4312 KB Ok
80 Correct 329 ms 11508 KB Ok
81 Correct 342 ms 11716 KB Ok
82 Correct 317 ms 11508 KB Ok
83 Correct 332 ms 11252 KB Ok
84 Correct 329 ms 11636 KB Ok
85 Correct 333 ms 11252 KB Ok
86 Correct 324 ms 11276 KB Ok
87 Correct 351 ms 11516 KB Ok
88 Correct 320 ms 11252 KB Ok
89 Correct 364 ms 11384 KB Ok
90 Correct 342 ms 11760 KB Ok
91 Correct 321 ms 11404 KB Ok
92 Correct 325 ms 11636 KB Ok
93 Correct 329 ms 11380 KB Ok
94 Correct 345 ms 11588 KB Ok
95 Correct 353 ms 10108 KB Ok
96 Correct 510 ms 14736 KB Ok
97 Correct 485 ms 12844 KB Ok
98 Correct 353 ms 11544 KB Ok
99 Correct 461 ms 11964 KB Ok
100 Correct 463 ms 12620 KB Ok
101 Correct 435 ms 12708 KB Ok
102 Correct 454 ms 12552 KB Ok
103 Correct 700 ms 13160 KB Ok
104 Correct 508 ms 14088 KB Ok
105 Correct 493 ms 14400 KB Ok
106 Correct 424 ms 12968 KB Ok
107 Correct 485 ms 13636 KB Ok
108 Correct 529 ms 14680 KB Ok
109 Correct 493 ms 14056 KB Ok
110 Correct 1903 ms 45300 KB Ok
111 Execution timed out 2039 ms 40000 KB Time limit exceeded
112 Halted 0 ms 0 KB -