oj.uz

Submission #369947

# Submission time Handle Problem Language Result Execution time Memory
369947 2021-02-22T19:29:24 Z nicolaalexandra Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 75432 KB 
#include <bits/stdc++.h>
#define DIM 2000010
using namespace std;

vector <int> L[DIM];
int v[DIM],g[DIM];
int n,m,k,t,i,j,idx,ok;

void dfs (int nod){
    v[nod] = ++idx;
    for (auto vecin : L[nod]){
        if (v[vecin])
            ok = 0;
        else dfs (vecin);
    }
}

int verif (int k){
    int i;

    for (i=0;i<=k;++i){
        L[i].clear();
        v[i] = g[i] = 0;
    }

    for (i=n;i<=k;++i){
        L[i].push_back(i-n);
        g[i-n]++;
    }

    for (i=m;i<=k;++i){
        L[i-m].push_back(i);
        g[i]++;
    }

    idx = 0, ok = 1;
    for (i=0;i<=k;++i){
        if (!g[i]){
            dfs (i);
            if (!ok)
                return 0;
        }}

    if (!idx)
        return 0;

    for (i=1;i<=k;++i){
        if (i >= n && v[i] >= v[i-n])
            return 0;
        if (i >= m && v[i] <= v[i-m])
            return 0;
    }

    return 1;
}

int main (){

    ios_base::sync_with_stdio(false);

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>t;
    for (;t--;){
        cin>>n>>m;
        if (n % m == 0){
            cout<<n-1<<"\n";
            for (i=1;i<=n-1;i++)
                cout<<"1 ";
            if (n > 1)
                cout<<"\n";
            continue;
        }

        if (m % n == 0){
            cout<<m-1<<"\n";
            for (i=1;i<=m-1;i++)
                cout<<"-1 ";
            if (m > 1)
                cout<<"\n";
            continue;
        }

        int st = min(n,m)-1, dr = 500000, sol = 0;
        while (st <= dr){
            int mid = (st+dr)>>1;
            if (verif(mid)){
                sol = mid;
                st = mid+1;
            } else dr = mid-1;
        }

        verif (sol);

        cout<<sol<<"\n";
        for (i=1;i<=sol;++i)
            cout<<v[i]-v[i-1]<<" ";
        if (sol)
            cout<<"\n";
    }

    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47340 KB Ok
2 Correct 28 ms 47340 KB Ok
3 Correct 28 ms 47340 KB Ok
4 Correct 28 ms 47340 KB Ok
5 Correct 28 ms 47340 KB Ok
6 Correct 28 ms 47340 KB Ok
7 Correct 28 ms 47340 KB Ok
8 Correct 29 ms 47340 KB Ok
9 Correct 28 ms 47340 KB Ok
10 Correct 28 ms 47340 KB Ok
11 Correct 28 ms 47340 KB Ok
12 Correct 28 ms 47340 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 57228 KB Ok
2 Correct 88 ms 57068 KB Ok
3 Correct 88 ms 57068 KB Ok
4 Correct 89 ms 57068 KB Ok
5 Correct 88 ms 57068 KB Ok
6 Correct 90 ms 57196 KB Ok
7 Correct 100 ms 57708 KB Ok
8 Correct 95 ms 57324 KB Ok
9 Correct 102 ms 57836 KB Ok
10 Correct 99 ms 57472 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 57068 KB Ok
2 Correct 28 ms 47340 KB Ok
3 Correct 80 ms 57068 KB Ok
4 Correct 97 ms 57068 KB Ok
5 Correct 99 ms 57068 KB Ok
6 Correct 107 ms 57068 KB Ok
7 Correct 99 ms 57068 KB Ok
8 Correct 126 ms 57068 KB Ok
9 Correct 99 ms 57068 KB Ok
10 Correct 106 ms 57068 KB Ok
11 Correct 99 ms 57068 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 57068 KB Ok
2 Correct 135 ms 57068 KB Ok
3 Correct 134 ms 57196 KB Ok
4 Correct 133 ms 57068 KB Ok
5 Correct 131 ms 57196 KB Ok
6 Correct 455 ms 67820 KB Ok
7 Correct 395 ms 67436 KB Ok
8 Correct 681 ms 71020 KB Ok
9 Correct 526 ms 69784 KB Ok
10 Correct 351 ms 63980 KB Ok
11 Correct 501 ms 70124 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47340 KB Ok
2 Correct 28 ms 47340 KB Ok
3 Correct 28 ms 47340 KB Ok
4 Correct 28 ms 47340 KB Ok
5 Correct 28 ms 47340 KB Ok
6 Correct 28 ms 47340 KB Ok
7 Correct 28 ms 47340 KB Ok
8 Correct 29 ms 47340 KB Ok
9 Correct 28 ms 47340 KB Ok
10 Correct 28 ms 47340 KB Ok
11 Correct 28 ms 47340 KB Ok
12 Correct 28 ms 47340 KB Ok
13 Correct 53 ms 57068 KB Ok
14 Correct 28 ms 47340 KB Ok
15 Correct 80 ms 57068 KB Ok
16 Correct 97 ms 57068 KB Ok
17 Correct 99 ms 57068 KB Ok
18 Correct 107 ms 57068 KB Ok
19 Correct 99 ms 57068 KB Ok
20 Correct 126 ms 57068 KB Ok
21 Correct 99 ms 57068 KB Ok
22 Correct 106 ms 57068 KB Ok
23 Correct 99 ms 57068 KB Ok
24 Correct 73 ms 57196 KB Ok
25 Correct 83 ms 57196 KB Ok
26 Correct 82 ms 57196 KB Ok
27 Correct 102 ms 57196 KB Ok
28 Correct 83 ms 57196 KB Ok
29 Correct 64 ms 57196 KB Ok
30 Correct 81 ms 57196 KB Ok
31 Correct 100 ms 57196 KB Ok
32 Correct 103 ms 57324 KB Ok
33 Correct 92 ms 57204 KB Ok
34 Correct 148 ms 57452 KB Ok
35 Correct 141 ms 57452 KB Ok
36 Correct 141 ms 57452 KB Ok
37 Correct 144 ms 57452 KB Ok
38 Correct 137 ms 57452 KB Ok
39 Correct 144 ms 57452 KB Ok
40 Correct 149 ms 57580 KB Ok
41 Correct 143 ms 57580 KB Ok
42 Correct 141 ms 57452 KB Ok
43 Correct 141 ms 57452 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47340 KB Ok
2 Correct 28 ms 47340 KB Ok
3 Correct 28 ms 47340 KB Ok
4 Correct 28 ms 47340 KB Ok
5 Correct 28 ms 47340 KB Ok
6 Correct 28 ms 47340 KB Ok
7 Correct 28 ms 47340 KB Ok
8 Correct 29 ms 47340 KB Ok
9 Correct 28 ms 47340 KB Ok
10 Correct 28 ms 47340 KB Ok
11 Correct 28 ms 47340 KB Ok
12 Correct 28 ms 47340 KB Ok
13 Correct 91 ms 57228 KB Ok
14 Correct 88 ms 57068 KB Ok
15 Correct 88 ms 57068 KB Ok
16 Correct 89 ms 57068 KB Ok
17 Correct 88 ms 57068 KB Ok
18 Correct 90 ms 57196 KB Ok
19 Correct 100 ms 57708 KB Ok
20 Correct 95 ms 57324 KB Ok
21 Correct 102 ms 57836 KB Ok
22 Correct 99 ms 57472 KB Ok
23 Correct 53 ms 57068 KB Ok
24 Correct 28 ms 47340 KB Ok
25 Correct 80 ms 57068 KB Ok
26 Correct 97 ms 57068 KB Ok
27 Correct 99 ms 57068 KB Ok
28 Correct 107 ms 57068 KB Ok
29 Correct 99 ms 57068 KB Ok
30 Correct 126 ms 57068 KB Ok
31 Correct 99 ms 57068 KB Ok
32 Correct 106 ms 57068 KB Ok
33 Correct 99 ms 57068 KB Ok
34 Correct 73 ms 57196 KB Ok
35 Correct 83 ms 57196 KB Ok
36 Correct 82 ms 57196 KB Ok
37 Correct 102 ms 57196 KB Ok
38 Correct 83 ms 57196 KB Ok
39 Correct 64 ms 57196 KB Ok
40 Correct 81 ms 57196 KB Ok
41 Correct 100 ms 57196 KB Ok
42 Correct 103 ms 57324 KB Ok
43 Correct 92 ms 57204 KB Ok
44 Correct 148 ms 57452 KB Ok
45 Correct 141 ms 57452 KB Ok
46 Correct 141 ms 57452 KB Ok
47 Correct 144 ms 57452 KB Ok
48 Correct 137 ms 57452 KB Ok
49 Correct 144 ms 57452 KB Ok
50 Correct 149 ms 57580 KB Ok
51 Correct 143 ms 57580 KB Ok
52 Correct 141 ms 57452 KB Ok
53 Correct 141 ms 57452 KB Ok
54 Correct 361 ms 59888 KB Ok
55 Correct 446 ms 60396 KB Ok
56 Correct 404 ms 60268 KB Ok
57 Correct 263 ms 59372 KB Ok
58 Correct 397 ms 59884 KB Ok
59 Correct 322 ms 59756 KB Ok
60 Correct 273 ms 59372 KB Ok
61 Correct 289 ms 59500 KB Ok
62 Correct 460 ms 60140 KB Ok
63 Correct 317 ms 59628 KB Ok
64 Correct 428 ms 60288 KB Ok
65 Correct 383 ms 60012 KB Ok
66 Correct 331 ms 59644 KB Ok
67 Correct 245 ms 59500 KB Ok
68 Correct 358 ms 59832 KB Ok
69 Correct 1012 ms 67504 KB Ok
70 Correct 929 ms 67948 KB Ok
71 Correct 949 ms 67820 KB Ok
72 Correct 956 ms 67436 KB Ok
73 Correct 1169 ms 67580 KB Ok
74 Correct 1004 ms 67692 KB Ok
75 Correct 954 ms 67436 KB Ok
76 Correct 1061 ms 67436 KB Ok
77 Correct 974 ms 67308 KB Ok
78 Correct 964 ms 67352 KB Ok
79 Correct 1150 ms 67692 KB Ok
80 Correct 893 ms 67856 KB Ok
81 Correct 1012 ms 67604 KB Ok
82 Correct 922 ms 67692 KB Ok
83 Correct 946 ms 67716 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47340 KB Ok
2 Correct 28 ms 47340 KB Ok
3 Correct 28 ms 47340 KB Ok
4 Correct 28 ms 47340 KB Ok
5 Correct 28 ms 47340 KB Ok
6 Correct 28 ms 47340 KB Ok
7 Correct 28 ms 47340 KB Ok
8 Correct 29 ms 47340 KB Ok
9 Correct 28 ms 47340 KB Ok
10 Correct 28 ms 47340 KB Ok
11 Correct 28 ms 47340 KB Ok
12 Correct 28 ms 47340 KB Ok
13 Correct 91 ms 57228 KB Ok
14 Correct 88 ms 57068 KB Ok
15 Correct 88 ms 57068 KB Ok
16 Correct 89 ms 57068 KB Ok
17 Correct 88 ms 57068 KB Ok
18 Correct 90 ms 57196 KB Ok
19 Correct 100 ms 57708 KB Ok
20 Correct 95 ms 57324 KB Ok
21 Correct 102 ms 57836 KB Ok
22 Correct 99 ms 57472 KB Ok
23 Correct 53 ms 57068 KB Ok
24 Correct 28 ms 47340 KB Ok
25 Correct 80 ms 57068 KB Ok
26 Correct 97 ms 57068 KB Ok
27 Correct 99 ms 57068 KB Ok
28 Correct 107 ms 57068 KB Ok
29 Correct 99 ms 57068 KB Ok
30 Correct 126 ms 57068 KB Ok
31 Correct 99 ms 57068 KB Ok
32 Correct 106 ms 57068 KB Ok
33 Correct 99 ms 57068 KB Ok
34 Correct 123 ms 57068 KB Ok
35 Correct 135 ms 57068 KB Ok
36 Correct 134 ms 57196 KB Ok
37 Correct 133 ms 57068 KB Ok
38 Correct 131 ms 57196 KB Ok
39 Correct 455 ms 67820 KB Ok
40 Correct 395 ms 67436 KB Ok
41 Correct 681 ms 71020 KB Ok
42 Correct 526 ms 69784 KB Ok
43 Correct 351 ms 63980 KB Ok
44 Correct 501 ms 70124 KB Ok
45 Correct 73 ms 57196 KB Ok
46 Correct 83 ms 57196 KB Ok
47 Correct 82 ms 57196 KB Ok
48 Correct 102 ms 57196 KB Ok
49 Correct 83 ms 57196 KB Ok
50 Correct 64 ms 57196 KB Ok
51 Correct 81 ms 57196 KB Ok
52 Correct 100 ms 57196 KB Ok
53 Correct 103 ms 57324 KB Ok
54 Correct 92 ms 57204 KB Ok
55 Correct 148 ms 57452 KB Ok
56 Correct 141 ms 57452 KB Ok
57 Correct 141 ms 57452 KB Ok
58 Correct 144 ms 57452 KB Ok
59 Correct 137 ms 57452 KB Ok
60 Correct 144 ms 57452 KB Ok
61 Correct 149 ms 57580 KB Ok
62 Correct 143 ms 57580 KB Ok
63 Correct 141 ms 57452 KB Ok
64 Correct 141 ms 57452 KB Ok
65 Correct 361 ms 59888 KB Ok
66 Correct 446 ms 60396 KB Ok
67 Correct 404 ms 60268 KB Ok
68 Correct 263 ms 59372 KB Ok
69 Correct 397 ms 59884 KB Ok
70 Correct 322 ms 59756 KB Ok
71 Correct 273 ms 59372 KB Ok
72 Correct 289 ms 59500 KB Ok
73 Correct 460 ms 60140 KB Ok
74 Correct 317 ms 59628 KB Ok
75 Correct 428 ms 60288 KB Ok
76 Correct 383 ms 60012 KB Ok
77 Correct 331 ms 59644 KB Ok
78 Correct 245 ms 59500 KB Ok
79 Correct 358 ms 59832 KB Ok
80 Correct 1012 ms 67504 KB Ok
81 Correct 929 ms 67948 KB Ok
82 Correct 949 ms 67820 KB Ok
83 Correct 956 ms 67436 KB Ok
84 Correct 1169 ms 67580 KB Ok
85 Correct 1004 ms 67692 KB Ok
86 Correct 954 ms 67436 KB Ok
87 Correct 1061 ms 67436 KB Ok
88 Correct 974 ms 67308 KB Ok
89 Correct 964 ms 67352 KB Ok
90 Correct 1150 ms 67692 KB Ok
91 Correct 893 ms 67856 KB Ok
92 Correct 1012 ms 67604 KB Ok
93 Correct 922 ms 67692 KB Ok
94 Correct 946 ms 67716 KB Ok
95 Correct 677 ms 64224 KB Ok
96 Correct 1161 ms 70628 KB Ok
97 Correct 1077 ms 65900 KB Ok
98 Correct 590 ms 63904 KB Ok
99 Correct 850 ms 65516 KB Ok
100 Correct 1108 ms 65900 KB Ok
101 Correct 985 ms 69260 KB Ok
102 Correct 1026 ms 65772 KB Ok
103 Correct 1213 ms 65996 KB Ok
104 Correct 1359 ms 70380 KB Ok
105 Correct 1239 ms 70252 KB Ok
106 Correct 1039 ms 69484 KB Ok
107 Correct 937 ms 69644 KB Ok
108 Correct 1494 ms 70440 KB Ok
109 Correct 1285 ms 69996 KB Ok
110 Execution timed out 2091 ms 75432 KB Time limit exceeded
111 Halted 0 ms 0 KB -