oj.uz

Submission #879429

# Submission time Handle Problem Language Result Execution time Memory
879429 2023-11-27T10:59:10 Z dimashhh Nice sequence (IZhO18_sequence) C++17
76 / 100
 854 ms 48072 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#pragma GCC optimize("Ofast","O3","unroll-loops")
#pragma GCC target("avx2")
const int N = 1e6 + 10, MOD = 998244353;
int timer = 1,pref[N],n,m,used[N];
vector<int> g[N],ord;
bool ok = 1;
void dfs(int v){
    used[v] = 1;
    for(int to:g[v]){
        if(used[to] == 1){
            ok = false;
        }
        if(!used[to]){
            dfs(to);
        }
    }
    used[v] = 2;
    ord.push_back(v);
}
bool can(int len){
  	assert(ok == 1);
    for(int i = 1;i <= len; i++){
        if(i - m >= 0){
            g[i - m].push_back(i);
        }
        if(i - n >= 0){
            g[i].push_back(i - n);
        }
    }
    for(int i = 0;i <= len;i++){
        if(!used[i]){
            dfs(i);
        }
    }
    reverse(ord.begin(),ord.end());
    for(auto i:ord){
        pref[i] = timer++;
    }
    timer = 1;
    ord.clear();
    for(int i = 0;i <= len;i++){
        g[i].clear();
    }
    for(int i = 0;i <= len;i++){
        used[i] = 0;
    }
  	bool ans = ok;
  	ok = 1;
    return ans;
}
void test(){
    cin >> n >> m;
    int l = 0,r = 35e4;
    while(r - l > 1){
        int mid = (l + r) >> 1;
        if(can(mid)){
            l = mid;
        }else{
            r = mid;
        }
    }
    can(l);
    cout << l << '\n';
    for(int i = 1;i <= l;i++){
        cout << pref[i] - pref[i - 1] << ' ';
    }
    cout << '\n';
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        test();
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 38856 KB Ok
2 Correct 76 ms 39124 KB Ok
3 Correct 118 ms 34004 KB Ok
4 Correct 116 ms 34248 KB Ok
5 Correct 131 ms 34000 KB Ok
6 Correct 97 ms 34884 KB Ok
7 Correct 121 ms 34020 KB Ok
8 Correct 105 ms 35112 KB Ok
9 Correct 138 ms 33952 KB Ok
10 Correct 111 ms 36076 KB Ok
11 Correct 124 ms 34004 KB Ok
12 Correct 120 ms 34004 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 38604 KB Ok
2 Correct 73 ms 38624 KB Ok
3 Correct 80 ms 38664 KB Ok
4 Correct 74 ms 38596 KB Ok
5 Correct 79 ms 38600 KB Ok
6 Correct 78 ms 39124 KB Ok
7 Correct 83 ms 38952 KB Ok
8 Correct 74 ms 38864 KB Ok
9 Correct 86 ms 39108 KB Ok
10 Correct 80 ms 38856 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 39120 KB Ok
2 Correct 70 ms 39124 KB Ok
3 Correct 72 ms 38600 KB Ok
4 Correct 74 ms 39124 KB Ok
5 Correct 72 ms 39120 KB Ok
6 Correct 78 ms 38740 KB Ok
7 Correct 70 ms 39096 KB Ok
8 Correct 74 ms 39092 KB Ok
9 Correct 72 ms 38600 KB Ok
10 Correct 74 ms 38596 KB Ok
11 Correct 78 ms 38600 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 39124 KB Ok
2 Correct 77 ms 39120 KB Ok
3 Correct 82 ms 39124 KB Ok
4 Correct 82 ms 39040 KB Ok
5 Correct 83 ms 39124 KB Ok
6 Correct 277 ms 42216 KB Ok
7 Correct 244 ms 44384 KB Ok
8 Correct 494 ms 46780 KB Ok
9 Correct 307 ms 44384 KB Ok
10 Correct 205 ms 41156 KB Ok
11 Correct 330 ms 47036 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 38856 KB Ok
2 Correct 76 ms 39124 KB Ok
3 Correct 118 ms 34004 KB Ok
4 Correct 116 ms 34248 KB Ok
5 Correct 131 ms 34000 KB Ok
6 Correct 97 ms 34884 KB Ok
7 Correct 121 ms 34020 KB Ok
8 Correct 105 ms 35112 KB Ok
9 Correct 138 ms 33952 KB Ok
10 Correct 111 ms 36076 KB Ok
11 Correct 124 ms 34004 KB Ok
12 Correct 120 ms 34004 KB Ok
13 Correct 35 ms 39120 KB Ok
14 Correct 70 ms 39124 KB Ok
15 Correct 72 ms 38600 KB Ok
16 Correct 74 ms 39124 KB Ok
17 Correct 72 ms 39120 KB Ok
18 Correct 78 ms 38740 KB Ok
19 Correct 70 ms 39096 KB Ok
20 Correct 74 ms 39092 KB Ok
21 Correct 72 ms 38600 KB Ok
22 Correct 74 ms 38596 KB Ok
23 Correct 78 ms 38600 KB Ok
24 Correct 101 ms 33736 KB Ok
25 Correct 113 ms 33976 KB Ok
26 Correct 104 ms 34260 KB Ok
27 Correct 100 ms 33996 KB Ok
28 Correct 105 ms 33744 KB Ok
29 Correct 97 ms 35264 KB Ok
30 Correct 107 ms 34004 KB Ok
31 Correct 105 ms 33912 KB Ok
32 Correct 106 ms 34004 KB Ok
33 Correct 115 ms 34100 KB Ok
34 Correct 157 ms 38824 KB Ok
35 Correct 116 ms 38864 KB Ok
36 Correct 131 ms 38868 KB Ok
37 Correct 119 ms 38856 KB Ok
38 Correct 122 ms 38860 KB Ok
39 Correct 129 ms 38780 KB Ok
40 Correct 125 ms 38868 KB Ok
41 Correct 115 ms 38864 KB Ok
42 Correct 131 ms 38868 KB Ok
43 Correct 122 ms 38864 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 38856 KB Ok
2 Correct 76 ms 39124 KB Ok
3 Correct 118 ms 34004 KB Ok
4 Correct 116 ms 34248 KB Ok
5 Correct 131 ms 34000 KB Ok
6 Correct 97 ms 34884 KB Ok
7 Correct 121 ms 34020 KB Ok
8 Correct 105 ms 35112 KB Ok
9 Correct 138 ms 33952 KB Ok
10 Correct 111 ms 36076 KB Ok
11 Correct 124 ms 34004 KB Ok
12 Correct 120 ms 34004 KB Ok
13 Correct 74 ms 38604 KB Ok
14 Correct 73 ms 38624 KB Ok
15 Correct 80 ms 38664 KB Ok
16 Correct 74 ms 38596 KB Ok
17 Correct 79 ms 38600 KB Ok
18 Correct 78 ms 39124 KB Ok
19 Correct 83 ms 38952 KB Ok
20 Correct 74 ms 38864 KB Ok
21 Correct 86 ms 39108 KB Ok
22 Correct 80 ms 38856 KB Ok
23 Correct 35 ms 39120 KB Ok
24 Correct 70 ms 39124 KB Ok
25 Correct 72 ms 38600 KB Ok
26 Correct 74 ms 39124 KB Ok
27 Correct 72 ms 39120 KB Ok
28 Correct 78 ms 38740 KB Ok
29 Correct 70 ms 39096 KB Ok
30 Correct 74 ms 39092 KB Ok
31 Correct 72 ms 38600 KB Ok
32 Correct 74 ms 38596 KB Ok
33 Correct 78 ms 38600 KB Ok
34 Correct 101 ms 33736 KB Ok
35 Correct 113 ms 33976 KB Ok
36 Correct 104 ms 34260 KB Ok
37 Correct 100 ms 33996 KB Ok
38 Correct 105 ms 33744 KB Ok
39 Correct 97 ms 35264 KB Ok
40 Correct 107 ms 34004 KB Ok
41 Correct 105 ms 33912 KB Ok
42 Correct 106 ms 34004 KB Ok
43 Correct 115 ms 34100 KB Ok
44 Correct 157 ms 38824 KB Ok
45 Correct 116 ms 38864 KB Ok
46 Correct 131 ms 38868 KB Ok
47 Correct 119 ms 38856 KB Ok
48 Correct 122 ms 38860 KB Ok
49 Correct 129 ms 38780 KB Ok
50 Correct 125 ms 38868 KB Ok
51 Correct 115 ms 38864 KB Ok
52 Correct 131 ms 38868 KB Ok
53 Correct 122 ms 38864 KB Ok
54 Correct 193 ms 35844 KB Ok
55 Correct 208 ms 36036 KB Ok
56 Correct 200 ms 36036 KB Ok
57 Correct 142 ms 35212 KB Ok
58 Correct 209 ms 35868 KB Ok
59 Correct 186 ms 35680 KB Ok
60 Correct 176 ms 35528 KB Ok
61 Correct 157 ms 35276 KB Ok
62 Correct 241 ms 36336 KB Ok
63 Correct 191 ms 35780 KB Ok
64 Correct 223 ms 36032 KB Ok
65 Correct 202 ms 35956 KB Ok
66 Correct 178 ms 35784 KB Ok
67 Correct 156 ms 35328 KB Ok
68 Correct 213 ms 35776 KB Ok
69 Correct 741 ms 42536 KB Ok
70 Correct 778 ms 43204 KB Ok
71 Correct 854 ms 42692 KB Ok
72 Correct 765 ms 42688 KB Ok
73 Correct 738 ms 43168 KB Ok
74 Correct 739 ms 42536 KB Ok
75 Correct 701 ms 42692 KB Ok
76 Correct 738 ms 42696 KB Ok
77 Correct 834 ms 42440 KB Ok
78 Correct 824 ms 42700 KB Ok
79 Correct 713 ms 43004 KB Ok
80 Correct 667 ms 42780 KB Ok
81 Correct 805 ms 42772 KB Ok
82 Correct 704 ms 42716 KB Ok
83 Correct 723 ms 42824 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 38856 KB Ok
2 Correct 76 ms 39124 KB Ok
3 Correct 118 ms 34004 KB Ok
4 Correct 116 ms 34248 KB Ok
5 Correct 131 ms 34000 KB Ok
6 Correct 97 ms 34884 KB Ok
7 Correct 121 ms 34020 KB Ok
8 Correct 105 ms 35112 KB Ok
9 Correct 138 ms 33952 KB Ok
10 Correct 111 ms 36076 KB Ok
11 Correct 124 ms 34004 KB Ok
12 Correct 120 ms 34004 KB Ok
13 Correct 74 ms 38604 KB Ok
14 Correct 73 ms 38624 KB Ok
15 Correct 80 ms 38664 KB Ok
16 Correct 74 ms 38596 KB Ok
17 Correct 79 ms 38600 KB Ok
18 Correct 78 ms 39124 KB Ok
19 Correct 83 ms 38952 KB Ok
20 Correct 74 ms 38864 KB Ok
21 Correct 86 ms 39108 KB Ok
22 Correct 80 ms 38856 KB Ok
23 Correct 35 ms 39120 KB Ok
24 Correct 70 ms 39124 KB Ok
25 Correct 72 ms 38600 KB Ok
26 Correct 74 ms 39124 KB Ok
27 Correct 72 ms 39120 KB Ok
28 Correct 78 ms 38740 KB Ok
29 Correct 70 ms 39096 KB Ok
30 Correct 74 ms 39092 KB Ok
31 Correct 72 ms 38600 KB Ok
32 Correct 74 ms 38596 KB Ok
33 Correct 78 ms 38600 KB Ok
34 Correct 72 ms 39124 KB Ok
35 Correct 77 ms 39120 KB Ok
36 Correct 82 ms 39124 KB Ok
37 Correct 82 ms 39040 KB Ok
38 Correct 83 ms 39124 KB Ok
39 Correct 277 ms 42216 KB Ok
40 Correct 244 ms 44384 KB Ok
41 Correct 494 ms 46780 KB Ok
42 Correct 307 ms 44384 KB Ok
43 Correct 205 ms 41156 KB Ok
44 Correct 330 ms 47036 KB Ok
45 Correct 101 ms 33736 KB Ok
46 Correct 113 ms 33976 KB Ok
47 Correct 104 ms 34260 KB Ok
48 Correct 100 ms 33996 KB Ok
49 Correct 105 ms 33744 KB Ok
50 Correct 97 ms 35264 KB Ok
51 Correct 107 ms 34004 KB Ok
52 Correct 105 ms 33912 KB Ok
53 Correct 106 ms 34004 KB Ok
54 Correct 115 ms 34100 KB Ok
55 Correct 157 ms 38824 KB Ok
56 Correct 116 ms 38864 KB Ok
57 Correct 131 ms 38868 KB Ok
58 Correct 119 ms 38856 KB Ok
59 Correct 122 ms 38860 KB Ok
60 Correct 129 ms 38780 KB Ok
61 Correct 125 ms 38868 KB Ok
62 Correct 115 ms 38864 KB Ok
63 Correct 131 ms 38868 KB Ok
64 Correct 122 ms 38864 KB Ok
65 Correct 193 ms 35844 KB Ok
66 Correct 208 ms 36036 KB Ok
67 Correct 200 ms 36036 KB Ok
68 Correct 142 ms 35212 KB Ok
69 Correct 209 ms 35868 KB Ok
70 Correct 186 ms 35680 KB Ok
71 Correct 176 ms 35528 KB Ok
72 Correct 157 ms 35276 KB Ok
73 Correct 241 ms 36336 KB Ok
74 Correct 191 ms 35780 KB Ok
75 Correct 223 ms 36032 KB Ok
76 Correct 202 ms 35956 KB Ok
77 Correct 178 ms 35784 KB Ok
78 Correct 156 ms 35328 KB Ok
79 Correct 213 ms 35776 KB Ok
80 Correct 741 ms 42536 KB Ok
81 Correct 778 ms 43204 KB Ok
82 Correct 854 ms 42692 KB Ok
83 Correct 765 ms 42688 KB Ok
84 Correct 738 ms 43168 KB Ok
85 Correct 739 ms 42536 KB Ok
86 Correct 701 ms 42692 KB Ok
87 Correct 738 ms 42696 KB Ok
88 Correct 834 ms 42440 KB Ok
89 Correct 824 ms 42700 KB Ok
90 Correct 713 ms 43004 KB Ok
91 Correct 667 ms 42780 KB Ok
92 Correct 805 ms 42772 KB Ok
93 Correct 704 ms 42716 KB Ok
94 Correct 723 ms 42824 KB Ok
95 Correct 434 ms 42272 KB Ok
96 Incorrect 697 ms 48072 KB Jury has the better answer : jans = 354419, pans = 349999
97 Halted 0 ms 0 KB -