oj.uz

Submission #879404

# Submission time Handle Problem Language Result Execution time Memory
879404 2023-11-27T10:20:13 Z vjudge1 Nice sequence (IZhO18_sequence) C++17
43 / 100
 171 ms 23248 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10, MOD = 998244353;

int timer = 1,pref[N],n,m,used[N];
vector<int> g[N],ord;
bool ok = false;
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){
    
    for(int i = 1;i <= len; i++){
        if(i - m >= 0){
            g[i - m].push_back(i);
            // cout << i - m << ' ' << i << '\n';
        }
        if(i - n >= 0){
            // cout << i << ' ' << i - n << '\n';
            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++;
    }
    bool res = ok;
    ok = true;
    timer = 1;
    ord.clear();
    for(int i = 0;i <= len;i++){
        g[i].clear();
    }
    for(int i = 0;i <= len;i++){
        used[i] = 0;
    }
    return res;
}
void test(){
    cin >> n >> m;
    int l = 0,r = 1e5;
    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 21 ms 19220 KB Ok
2 Correct 22 ms 19292 KB Ok
3 Correct 28 ms 16984 KB Ok
4 Correct 23 ms 17116 KB Ok
5 Correct 23 ms 16988 KB Ok
6 Correct 21 ms 17372 KB Ok
7 Correct 22 ms 17020 KB Ok
8 Correct 21 ms 17500 KB Ok
9 Correct 21 ms 16984 KB Ok
10 Correct 20 ms 17884 KB Ok
11 Correct 22 ms 16924 KB Ok
12 Correct 20 ms 16988 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19164 KB Ok
2 Correct 22 ms 19160 KB Ok
3 Correct 22 ms 19164 KB Ok
4 Correct 23 ms 19164 KB Ok
5 Correct 21 ms 19096 KB Ok
6 Correct 23 ms 19164 KB Ok
7 Correct 46 ms 19264 KB Ok
8 Correct 32 ms 19436 KB Ok
9 Correct 40 ms 19672 KB Ok
10 Correct 30 ms 19160 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19292 KB Ok
2 Correct 22 ms 19292 KB Ok
3 Correct 22 ms 19164 KB Ok
4 Correct 21 ms 19288 KB Ok
5 Correct 22 ms 19292 KB Ok
6 Correct 21 ms 19164 KB Ok
7 Correct 21 ms 19292 KB Ok
8 Correct 21 ms 19292 KB Ok
9 Correct 22 ms 19164 KB Ok
10 Correct 21 ms 19160 KB Ok
11 Correct 22 ms 19164 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 19288 KB Ok
2 Correct 25 ms 19292 KB Ok
3 Correct 27 ms 19292 KB Ok
4 Correct 24 ms 19292 KB Ok
5 Correct 23 ms 19288 KB Ok
6 Incorrect 164 ms 23248 KB Jury has the better answer : jans = 166803, pans = 49999
7 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19220 KB Ok
2 Correct 22 ms 19292 KB Ok
3 Correct 28 ms 16984 KB Ok
4 Correct 23 ms 17116 KB Ok
5 Correct 23 ms 16988 KB Ok
6 Correct 21 ms 17372 KB Ok
7 Correct 22 ms 17020 KB Ok
8 Correct 21 ms 17500 KB Ok
9 Correct 21 ms 16984 KB Ok
10 Correct 20 ms 17884 KB Ok
11 Correct 22 ms 16924 KB Ok
12 Correct 20 ms 16988 KB Ok
13 Correct 12 ms 19292 KB Ok
14 Correct 22 ms 19292 KB Ok
15 Correct 22 ms 19164 KB Ok
16 Correct 21 ms 19288 KB Ok
17 Correct 22 ms 19292 KB Ok
18 Correct 21 ms 19164 KB Ok
19 Correct 21 ms 19292 KB Ok
20 Correct 21 ms 19292 KB Ok
21 Correct 22 ms 19164 KB Ok
22 Correct 21 ms 19160 KB Ok
23 Correct 22 ms 19164 KB Ok
24 Correct 28 ms 16860 KB Ok
25 Correct 29 ms 16860 KB Ok
26 Correct 29 ms 17056 KB Ok
27 Correct 29 ms 17108 KB Ok
28 Correct 26 ms 16860 KB Ok
29 Correct 29 ms 17680 KB Ok
30 Correct 30 ms 17116 KB Ok
31 Correct 29 ms 16860 KB Ok
32 Correct 27 ms 16988 KB Ok
33 Correct 28 ms 16860 KB Ok
34 Correct 46 ms 19340 KB Ok
35 Correct 36 ms 19164 KB Ok
36 Correct 40 ms 19348 KB Ok
37 Correct 44 ms 19552 KB Ok
38 Correct 38 ms 19164 KB Ok
39 Correct 42 ms 19164 KB Ok
40 Correct 41 ms 19164 KB Ok
41 Correct 38 ms 19632 KB Ok
42 Correct 42 ms 19160 KB Ok
43 Correct 46 ms 19328 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19220 KB Ok
2 Correct 22 ms 19292 KB Ok
3 Correct 28 ms 16984 KB Ok
4 Correct 23 ms 17116 KB Ok
5 Correct 23 ms 16988 KB Ok
6 Correct 21 ms 17372 KB Ok
7 Correct 22 ms 17020 KB Ok
8 Correct 21 ms 17500 KB Ok
9 Correct 21 ms 16984 KB Ok
10 Correct 20 ms 17884 KB Ok
11 Correct 22 ms 16924 KB Ok
12 Correct 20 ms 16988 KB Ok
13 Correct 21 ms 19164 KB Ok
14 Correct 22 ms 19160 KB Ok
15 Correct 22 ms 19164 KB Ok
16 Correct 23 ms 19164 KB Ok
17 Correct 21 ms 19096 KB Ok
18 Correct 23 ms 19164 KB Ok
19 Correct 46 ms 19264 KB Ok
20 Correct 32 ms 19436 KB Ok
21 Correct 40 ms 19672 KB Ok
22 Correct 30 ms 19160 KB Ok
23 Correct 12 ms 19292 KB Ok
24 Correct 22 ms 19292 KB Ok
25 Correct 22 ms 19164 KB Ok
26 Correct 21 ms 19288 KB Ok
27 Correct 22 ms 19292 KB Ok
28 Correct 21 ms 19164 KB Ok
29 Correct 21 ms 19292 KB Ok
30 Correct 21 ms 19292 KB Ok
31 Correct 22 ms 19164 KB Ok
32 Correct 21 ms 19160 KB Ok
33 Correct 22 ms 19164 KB Ok
34 Correct 28 ms 16860 KB Ok
35 Correct 29 ms 16860 KB Ok
36 Correct 29 ms 17056 KB Ok
37 Correct 29 ms 17108 KB Ok
38 Correct 26 ms 16860 KB Ok
39 Correct 29 ms 17680 KB Ok
40 Correct 30 ms 17116 KB Ok
41 Correct 29 ms 16860 KB Ok
42 Correct 27 ms 16988 KB Ok
43 Correct 28 ms 16860 KB Ok
44 Correct 46 ms 19340 KB Ok
45 Correct 36 ms 19164 KB Ok
46 Correct 40 ms 19348 KB Ok
47 Correct 44 ms 19552 KB Ok
48 Correct 38 ms 19164 KB Ok
49 Correct 42 ms 19164 KB Ok
50 Correct 41 ms 19164 KB Ok
51 Correct 38 ms 19632 KB Ok
52 Correct 42 ms 19160 KB Ok
53 Correct 46 ms 19328 KB Ok
54 Incorrect 171 ms 20300 KB Jury has the better answer : jans = 82899, pans = 49999
55 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19220 KB Ok
2 Correct 22 ms 19292 KB Ok
3 Correct 28 ms 16984 KB Ok
4 Correct 23 ms 17116 KB Ok
5 Correct 23 ms 16988 KB Ok
6 Correct 21 ms 17372 KB Ok
7 Correct 22 ms 17020 KB Ok
8 Correct 21 ms 17500 KB Ok
9 Correct 21 ms 16984 KB Ok
10 Correct 20 ms 17884 KB Ok
11 Correct 22 ms 16924 KB Ok
12 Correct 20 ms 16988 KB Ok
13 Correct 21 ms 19164 KB Ok
14 Correct 22 ms 19160 KB Ok
15 Correct 22 ms 19164 KB Ok
16 Correct 23 ms 19164 KB Ok
17 Correct 21 ms 19096 KB Ok
18 Correct 23 ms 19164 KB Ok
19 Correct 46 ms 19264 KB Ok
20 Correct 32 ms 19436 KB Ok
21 Correct 40 ms 19672 KB Ok
22 Correct 30 ms 19160 KB Ok
23 Correct 12 ms 19292 KB Ok
24 Correct 22 ms 19292 KB Ok
25 Correct 22 ms 19164 KB Ok
26 Correct 21 ms 19288 KB Ok
27 Correct 22 ms 19292 KB Ok
28 Correct 21 ms 19164 KB Ok
29 Correct 21 ms 19292 KB Ok
30 Correct 21 ms 19292 KB Ok
31 Correct 22 ms 19164 KB Ok
32 Correct 21 ms 19160 KB Ok
33 Correct 22 ms 19164 KB Ok
34 Correct 22 ms 19288 KB Ok
35 Correct 25 ms 19292 KB Ok
36 Correct 27 ms 19292 KB Ok
37 Correct 24 ms 19292 KB Ok
38 Correct 23 ms 19288 KB Ok
39 Incorrect 164 ms 23248 KB Jury has the better answer : jans = 166803, pans = 49999
40 Halted 0 ms 0 KB -