oj.uz

Submission #369927

# Submission time Handle Problem Language Result Execution time Memory
369927 2021-02-22T18:40:04 Z nicolaalexandra Nice sequence (IZhO18_sequence) C++14
15 / 100
 211 ms 44140 KB 
#include <bits/stdc++.h>
#define DIM 1000010
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 (!idx)
        return 0;

    return ok;
}

int main (){

    //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 = 1000000, 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]<<" ";
        cout<<"\n";
    }

    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23788 KB Ok
2 Correct 14 ms 23788 KB Ok
3 Correct 14 ms 23788 KB Ok
4 Correct 14 ms 23788 KB Ok
5 Correct 15 ms 23788 KB Ok
6 Correct 14 ms 23788 KB Ok
7 Correct 15 ms 23788 KB Ok
8 Correct 14 ms 23788 KB Ok
9 Correct 14 ms 23788 KB Ok
10 Correct 14 ms 23788 KB Ok
11 Correct 14 ms 23788 KB Ok
12 Correct 14 ms 23788 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 43500 KB Ok
2 Correct 144 ms 43372 KB Ok
3 Correct 140 ms 43372 KB Ok
4 Correct 139 ms 43372 KB Ok
5 Correct 139 ms 43372 KB Ok
6 Correct 141 ms 43500 KB Ok
7 Correct 153 ms 44140 KB Ok
8 Correct 147 ms 43628 KB Ok
9 Correct 155 ms 44140 KB Ok
10 Correct 147 ms 43812 KB Ok

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 43372 KB Ok
2 Correct 14 ms 23788 KB Ok
3 Correct 120 ms 43372 KB Ok
4 Correct 158 ms 43372 KB Ok
5 Incorrect 158 ms 43372 KB there is incorrect sequence
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 211 ms 43372 KB there is incorrect sequence
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23788 KB Ok
2 Correct 14 ms 23788 KB Ok
3 Correct 14 ms 23788 KB Ok
4 Correct 14 ms 23788 KB Ok
5 Correct 15 ms 23788 KB Ok
6 Correct 14 ms 23788 KB Ok
7 Correct 15 ms 23788 KB Ok
8 Correct 14 ms 23788 KB Ok
9 Correct 14 ms 23788 KB Ok
10 Correct 14 ms 23788 KB Ok
11 Correct 14 ms 23788 KB Ok
12 Correct 14 ms 23788 KB Ok
13 Correct 69 ms 43372 KB Ok
14 Correct 14 ms 23788 KB Ok
15 Correct 120 ms 43372 KB Ok
16 Correct 158 ms 43372 KB Ok
17 Incorrect 158 ms 43372 KB there is incorrect sequence
18 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23788 KB Ok
2 Correct 14 ms 23788 KB Ok
3 Correct 14 ms 23788 KB Ok
4 Correct 14 ms 23788 KB Ok
5 Correct 15 ms 23788 KB Ok
6 Correct 14 ms 23788 KB Ok
7 Correct 15 ms 23788 KB Ok
8 Correct 14 ms 23788 KB Ok
9 Correct 14 ms 23788 KB Ok
10 Correct 14 ms 23788 KB Ok
11 Correct 14 ms 23788 KB Ok
12 Correct 14 ms 23788 KB Ok
13 Correct 142 ms 43500 KB Ok
14 Correct 144 ms 43372 KB Ok
15 Correct 140 ms 43372 KB Ok
16 Correct 139 ms 43372 KB Ok
17 Correct 139 ms 43372 KB Ok
18 Correct 141 ms 43500 KB Ok
19 Correct 153 ms 44140 KB Ok
20 Correct 147 ms 43628 KB Ok
21 Correct 155 ms 44140 KB Ok
22 Correct 147 ms 43812 KB Ok
23 Correct 69 ms 43372 KB Ok
24 Correct 14 ms 23788 KB Ok
25 Correct 120 ms 43372 KB Ok
26 Correct 158 ms 43372 KB Ok
27 Incorrect 158 ms 43372 KB there is incorrect sequence
28 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23788 KB Ok
2 Correct 14 ms 23788 KB Ok
3 Correct 14 ms 23788 KB Ok
4 Correct 14 ms 23788 KB Ok
5 Correct 15 ms 23788 KB Ok
6 Correct 14 ms 23788 KB Ok
7 Correct 15 ms 23788 KB Ok
8 Correct 14 ms 23788 KB Ok
9 Correct 14 ms 23788 KB Ok
10 Correct 14 ms 23788 KB Ok
11 Correct 14 ms 23788 KB Ok
12 Correct 14 ms 23788 KB Ok
13 Correct 142 ms 43500 KB Ok
14 Correct 144 ms 43372 KB Ok
15 Correct 140 ms 43372 KB Ok
16 Correct 139 ms 43372 KB Ok
17 Correct 139 ms 43372 KB Ok
18 Correct 141 ms 43500 KB Ok
19 Correct 153 ms 44140 KB Ok
20 Correct 147 ms 43628 KB Ok
21 Correct 155 ms 44140 KB Ok
22 Correct 147 ms 43812 KB Ok
23 Correct 69 ms 43372 KB Ok
24 Correct 14 ms 23788 KB Ok
25 Correct 120 ms 43372 KB Ok
26 Correct 158 ms 43372 KB Ok
27 Incorrect 158 ms 43372 KB there is incorrect sequence
28 Halted 0 ms 0 KB -