oj.uz

Submission #91951

# Submission time Handle Problem Language Result Execution time Memory
91951 2018-12-31T16:03:11 Z popovicirobert Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 51120 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int INF = 5e8;
const int MAXN = (int) 2e5;

vector <int> g[2 * MAXN + 1];
char vis[2 * MAXN + 1];

void dfs(int nod, bool &ok) {
    vis[nod] = 1;
    for(auto it : g[nod]) {
        if(vis[it] == 0) {
            dfs(it, ok);
        }
        else if(vis[it] == 1) {
            ok = 0;
        }
        if(ok == 0) {
            return ;
        }
    }
    vis[nod] = 2;
}

inline bool check(int len, int n, int m) {
    int i;
    for(i = 0; i <= len; i++) {
        g[i].clear();
        vis[i] = 0;
    }
    for(i = 1; i <= len; i++) {
        if(i >= n) {
            g[i - n].push_back(i);
        }
        if(i >= m) {
            g[i].push_back(i - m);
        }
    }
    bool ok = 1;
    for(i = 0; i <= len; i++) {
        if(vis[i] == 0) {
            dfs(i, ok);
        }
    }
    return ok;
}

inline int get(int n, int m) {
    int res = 0;
    for(int step = 1 << 18; step; step >>= 1) {
        if(res + step <= n + m && check(res + step, n, m)) {
            res += step;
        }
    }
    return res;
}

vector <int> aux[2 * MAXN + 1];
vector <int> ord;
int sp[2 * MAXN + 1];

void dfs1(int nod) {
    vis[nod] = 1;
    for(auto it : aux[nod]) {
        if(vis[it] == 0) {
            dfs1(it);
        }
    }
    ord.push_back(nod);
}

inline void solve(int sz, int n, int m) {
    int i;
    for(i = 0; i <= sz; i++) {
        aux[i].clear();
        vis[i] = 0;
        if(i - n >= 0) {
            aux[i - n].push_back(i);
        }
        if(i - m >= 0) {
            aux[i].push_back(i - m);
        }
    }
    ord.clear();
    for(i = 0; i <= sz; i++) {
        if(vis[i] == 0) {
            dfs1(i);
        }
    }
    int val = -INF;
    for(auto it : ord) {
        if(it == 0) {
            val = max(val, 0);
            sp[it] = 0;
            val++;
            continue;
        }
        for(auto itr : aux[it]) {
            val = max(val, sp[itr] + 1);
        }
        sp[it] = val;
        val++;
    }
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int t, i, j;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> t;
    while(t > 0) {
        t--;
        int n, m;
        cin >> n >> m;
        int mn = min(n, m), mx = max(n, m);
        if(mx % mn == 0) {
            cout << mx - 1 << "\n";
            int sign = 1;
            if(mn == n) {
                sign = -1;
            }
            for(i = 1; i < mx; i++) {
                cout << sign << " ";
            }
            if(mx > 1) {
                cout << "\n";
            }
            continue;
        }
        int sz = get(n, m);
        solve(sz, n, m);
        cout << sz << "\n";
        for(i = 1; i <= sz; i++) {
            cout << sp[i] - sp[i - 1] << " ";
        }
        cout << "\n";
    }
    //cin.close();
    //cout.close();
    return 0;
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:117:15: warning: unused variable 'j' [-Wunused-variable]
     int t, i, j;
               ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19192 KB Ok
2 Correct 15 ms 19192 KB Ok
3 Correct 16 ms 19164 KB Ok
4 Correct 17 ms 19192 KB Ok
5 Correct 21 ms 19196 KB Ok
6 Correct 21 ms 19192 KB Ok
7 Correct 18 ms 19196 KB Ok
8 Correct 19 ms 19152 KB Ok
9 Correct 18 ms 19064 KB Ok
10 Correct 19 ms 19064 KB Ok
11 Correct 18 ms 19064 KB Ok
12 Correct 18 ms 19064 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19064 KB Ok
2 Correct 19 ms 19144 KB Ok
3 Correct 18 ms 19064 KB Ok
4 Correct 17 ms 19164 KB Ok
5 Correct 16 ms 19192 KB Ok
6 Correct 21 ms 19448 KB Ok
7 Correct 33 ms 20728 KB Ok
8 Correct 25 ms 19832 KB Ok
9 Correct 36 ms 20856 KB Ok
10 Correct 30 ms 20216 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19192 KB Ok
2 Correct 20 ms 19164 KB Ok
3 Correct 18 ms 19068 KB Ok
4 Correct 18 ms 19164 KB Ok
5 Correct 18 ms 19064 KB Ok
6 Correct 18 ms 19164 KB Ok
7 Correct 18 ms 19064 KB Ok
8 Correct 18 ms 19064 KB Ok
9 Correct 19 ms 19192 KB Ok
10 Correct 16 ms 19192 KB Ok
11 Correct 18 ms 19068 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19064 KB Ok
2 Correct 19 ms 19192 KB Ok
3 Correct 18 ms 19192 KB Ok
4 Correct 18 ms 19192 KB Ok
5 Correct 18 ms 19120 KB Ok
6 Correct 315 ms 43400 KB Ok
7 Correct 287 ms 45036 KB Ok
8 Correct 554 ms 49552 KB Ok
9 Correct 395 ms 45904 KB Ok
10 Correct 205 ms 33844 KB Ok
11 Correct 397 ms 47304 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19192 KB Ok
2 Correct 15 ms 19192 KB Ok
3 Correct 16 ms 19164 KB Ok
4 Correct 17 ms 19192 KB Ok
5 Correct 21 ms 19196 KB Ok
6 Correct 21 ms 19192 KB Ok
7 Correct 18 ms 19196 KB Ok
8 Correct 19 ms 19152 KB Ok
9 Correct 18 ms 19064 KB Ok
10 Correct 19 ms 19064 KB Ok
11 Correct 18 ms 19064 KB Ok
12 Correct 18 ms 19064 KB Ok
13 Correct 17 ms 19192 KB Ok
14 Correct 20 ms 19164 KB Ok
15 Correct 18 ms 19068 KB Ok
16 Correct 18 ms 19164 KB Ok
17 Correct 18 ms 19064 KB Ok
18 Correct 18 ms 19164 KB Ok
19 Correct 18 ms 19064 KB Ok
20 Correct 18 ms 19064 KB Ok
21 Correct 19 ms 19192 KB Ok
22 Correct 16 ms 19192 KB Ok
23 Correct 18 ms 19068 KB Ok
24 Correct 21 ms 19320 KB Ok
25 Correct 23 ms 19448 KB Ok
26 Correct 22 ms 19448 KB Ok
27 Correct 22 ms 19448 KB Ok
28 Correct 21 ms 19464 KB Ok
29 Correct 21 ms 19320 KB Ok
30 Correct 21 ms 19320 KB Ok
31 Correct 22 ms 19448 KB Ok
32 Correct 24 ms 19448 KB Ok
33 Correct 22 ms 19452 KB Ok
34 Correct 27 ms 19704 KB Ok
35 Correct 30 ms 19832 KB Ok
36 Correct 29 ms 19832 KB Ok
37 Correct 28 ms 19836 KB Ok
38 Correct 27 ms 19832 KB Ok
39 Correct 29 ms 19832 KB Ok
40 Correct 30 ms 19836 KB Ok
41 Correct 28 ms 19832 KB Ok
42 Correct 32 ms 19832 KB Ok
43 Correct 31 ms 19832 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19192 KB Ok
2 Correct 15 ms 19192 KB Ok
3 Correct 16 ms 19164 KB Ok
4 Correct 17 ms 19192 KB Ok
5 Correct 21 ms 19196 KB Ok
6 Correct 21 ms 19192 KB Ok
7 Correct 18 ms 19196 KB Ok
8 Correct 19 ms 19152 KB Ok
9 Correct 18 ms 19064 KB Ok
10 Correct 19 ms 19064 KB Ok
11 Correct 18 ms 19064 KB Ok
12 Correct 18 ms 19064 KB Ok
13 Correct 19 ms 19064 KB Ok
14 Correct 19 ms 19144 KB Ok
15 Correct 18 ms 19064 KB Ok
16 Correct 17 ms 19164 KB Ok
17 Correct 16 ms 19192 KB Ok
18 Correct 21 ms 19448 KB Ok
19 Correct 33 ms 20728 KB Ok
20 Correct 25 ms 19832 KB Ok
21 Correct 36 ms 20856 KB Ok
22 Correct 30 ms 20216 KB Ok
23 Correct 17 ms 19192 KB Ok
24 Correct 20 ms 19164 KB Ok
25 Correct 18 ms 19068 KB Ok
26 Correct 18 ms 19164 KB Ok
27 Correct 18 ms 19064 KB Ok
28 Correct 18 ms 19164 KB Ok
29 Correct 18 ms 19064 KB Ok
30 Correct 18 ms 19064 KB Ok
31 Correct 19 ms 19192 KB Ok
32 Correct 16 ms 19192 KB Ok
33 Correct 18 ms 19068 KB Ok
34 Correct 21 ms 19320 KB Ok
35 Correct 23 ms 19448 KB Ok
36 Correct 22 ms 19448 KB Ok
37 Correct 22 ms 19448 KB Ok
38 Correct 21 ms 19464 KB Ok
39 Correct 21 ms 19320 KB Ok
40 Correct 21 ms 19320 KB Ok
41 Correct 22 ms 19448 KB Ok
42 Correct 24 ms 19448 KB Ok
43 Correct 22 ms 19452 KB Ok
44 Correct 27 ms 19704 KB Ok
45 Correct 30 ms 19832 KB Ok
46 Correct 29 ms 19832 KB Ok
47 Correct 28 ms 19836 KB Ok
48 Correct 27 ms 19832 KB Ok
49 Correct 29 ms 19832 KB Ok
50 Correct 30 ms 19836 KB Ok
51 Correct 28 ms 19832 KB Ok
52 Correct 32 ms 19832 KB Ok
53 Correct 31 ms 19832 KB Ok
54 Correct 337 ms 27540 KB Ok
55 Correct 451 ms 27888 KB Ok
56 Correct 408 ms 27848 KB Ok
57 Correct 215 ms 26704 KB Ok
58 Correct 282 ms 27376 KB Ok
59 Correct 222 ms 26968 KB Ok
60 Correct 184 ms 26352 KB Ok
61 Correct 228 ms 27124 KB Ok
62 Correct 325 ms 27488 KB Ok
63 Correct 265 ms 26708 KB Ok
64 Correct 373 ms 27632 KB Ok
65 Correct 314 ms 27528 KB Ok
66 Correct 251 ms 27252 KB Ok
67 Correct 211 ms 27124 KB Ok
68 Correct 414 ms 27360 KB Ok
69 Correct 965 ms 38168 KB Ok
70 Correct 741 ms 39664 KB Ok
71 Correct 870 ms 39072 KB Ok
72 Correct 974 ms 38256 KB Ok
73 Correct 672 ms 39028 KB Ok
74 Correct 763 ms 38260 KB Ok
75 Correct 946 ms 37724 KB Ok
76 Correct 860 ms 39008 KB Ok
77 Correct 909 ms 37748 KB Ok
78 Correct 712 ms 38812 KB Ok
79 Correct 852 ms 39264 KB Ok
80 Correct 866 ms 39440 KB Ok
81 Correct 768 ms 38752 KB Ok
82 Correct 775 ms 39152 KB Ok
83 Correct 896 ms 37740 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19192 KB Ok
2 Correct 15 ms 19192 KB Ok
3 Correct 16 ms 19164 KB Ok
4 Correct 17 ms 19192 KB Ok
5 Correct 21 ms 19196 KB Ok
6 Correct 21 ms 19192 KB Ok
7 Correct 18 ms 19196 KB Ok
8 Correct 19 ms 19152 KB Ok
9 Correct 18 ms 19064 KB Ok
10 Correct 19 ms 19064 KB Ok
11 Correct 18 ms 19064 KB Ok
12 Correct 18 ms 19064 KB Ok
13 Correct 19 ms 19064 KB Ok
14 Correct 19 ms 19144 KB Ok
15 Correct 18 ms 19064 KB Ok
16 Correct 17 ms 19164 KB Ok
17 Correct 16 ms 19192 KB Ok
18 Correct 21 ms 19448 KB Ok
19 Correct 33 ms 20728 KB Ok
20 Correct 25 ms 19832 KB Ok
21 Correct 36 ms 20856 KB Ok
22 Correct 30 ms 20216 KB Ok
23 Correct 17 ms 19192 KB Ok
24 Correct 20 ms 19164 KB Ok
25 Correct 18 ms 19068 KB Ok
26 Correct 18 ms 19164 KB Ok
27 Correct 18 ms 19064 KB Ok
28 Correct 18 ms 19164 KB Ok
29 Correct 18 ms 19064 KB Ok
30 Correct 18 ms 19064 KB Ok
31 Correct 19 ms 19192 KB Ok
32 Correct 16 ms 19192 KB Ok
33 Correct 18 ms 19068 KB Ok
34 Correct 15 ms 19064 KB Ok
35 Correct 19 ms 19192 KB Ok
36 Correct 18 ms 19192 KB Ok
37 Correct 18 ms 19192 KB Ok
38 Correct 18 ms 19120 KB Ok
39 Correct 315 ms 43400 KB Ok
40 Correct 287 ms 45036 KB Ok
41 Correct 554 ms 49552 KB Ok
42 Correct 395 ms 45904 KB Ok
43 Correct 205 ms 33844 KB Ok
44 Correct 397 ms 47304 KB Ok
45 Correct 21 ms 19320 KB Ok
46 Correct 23 ms 19448 KB Ok
47 Correct 22 ms 19448 KB Ok
48 Correct 22 ms 19448 KB Ok
49 Correct 21 ms 19464 KB Ok
50 Correct 21 ms 19320 KB Ok
51 Correct 21 ms 19320 KB Ok
52 Correct 22 ms 19448 KB Ok
53 Correct 24 ms 19448 KB Ok
54 Correct 22 ms 19452 KB Ok
55 Correct 27 ms 19704 KB Ok
56 Correct 30 ms 19832 KB Ok
57 Correct 29 ms 19832 KB Ok
58 Correct 28 ms 19836 KB Ok
59 Correct 27 ms 19832 KB Ok
60 Correct 29 ms 19832 KB Ok
61 Correct 30 ms 19836 KB Ok
62 Correct 28 ms 19832 KB Ok
63 Correct 32 ms 19832 KB Ok
64 Correct 31 ms 19832 KB Ok
65 Correct 337 ms 27540 KB Ok
66 Correct 451 ms 27888 KB Ok
67 Correct 408 ms 27848 KB Ok
68 Correct 215 ms 26704 KB Ok
69 Correct 282 ms 27376 KB Ok
70 Correct 222 ms 26968 KB Ok
71 Correct 184 ms 26352 KB Ok
72 Correct 228 ms 27124 KB Ok
73 Correct 325 ms 27488 KB Ok
74 Correct 265 ms 26708 KB Ok
75 Correct 373 ms 27632 KB Ok
76 Correct 314 ms 27528 KB Ok
77 Correct 251 ms 27252 KB Ok
78 Correct 211 ms 27124 KB Ok
79 Correct 414 ms 27360 KB Ok
80 Correct 965 ms 38168 KB Ok
81 Correct 741 ms 39664 KB Ok
82 Correct 870 ms 39072 KB Ok
83 Correct 974 ms 38256 KB Ok
84 Correct 672 ms 39028 KB Ok
85 Correct 763 ms 38260 KB Ok
86 Correct 946 ms 37724 KB Ok
87 Correct 860 ms 39008 KB Ok
88 Correct 909 ms 37748 KB Ok
89 Correct 712 ms 38812 KB Ok
90 Correct 852 ms 39264 KB Ok
91 Correct 866 ms 39440 KB Ok
92 Correct 768 ms 38752 KB Ok
93 Correct 775 ms 39152 KB Ok
94 Correct 896 ms 37740 KB Ok
95 Correct 973 ms 41304 KB Ok
96 Correct 1668 ms 50884 KB Ok
97 Correct 1493 ms 46156 KB Ok
98 Correct 747 ms 45752 KB Ok
99 Correct 1037 ms 46144 KB Ok
100 Correct 1031 ms 43612 KB Ok
101 Correct 1539 ms 48264 KB Ok
102 Correct 1593 ms 45668 KB Ok
103 Correct 1114 ms 47336 KB Ok
104 Correct 1800 ms 49588 KB Ok
105 Correct 1634 ms 50204 KB Ok
106 Correct 1479 ms 51120 KB Ok
107 Correct 1477 ms 48936 KB Ok
108 Execution timed out 2057 ms 47356 KB Time limit exceeded
109 Halted 0 ms 0 KB -