oj.uz

Submission #91960

# Submission time Handle Problem Language Result Execution time Memory
91960 2018-12-31T16:12:41 Z popovicirobert Nice sequence (IZhO18_sequence) C++14
30 / 100
 233 ms 33908 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 && ok; i++) {
        if(vis[i] == 0) {
            dfs(i, ok);
        }
    }
    return ok;
}

inline int get(int n, int m) {
    int res = n + m - 2;
    while(check(res, n, m)) {
        res++;
    }
    return res - 1;
}

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

void dfs1(int nod) {
    vis[nod] = 1;
    for(auto it : g[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++) {
        g[i].clear();
        vis[i] = 0;
        if(i - n >= 0) {
            g[i - n].push_back(i);
        }
        if(i - m >= 0) {
            g[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 : g[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:114: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 10 ms 9720 KB Ok
2 Correct 9 ms 9720 KB Ok
3 Correct 10 ms 9720 KB Ok
4 Correct 9 ms 9720 KB Ok
5 Correct 10 ms 9724 KB Ok
6 Correct 10 ms 9720 KB Ok
7 Correct 9 ms 9720 KB Ok
8 Correct 9 ms 9720 KB Ok
9 Correct 10 ms 9720 KB Ok
10 Correct 9 ms 9720 KB Ok
11 Correct 9 ms 9720 KB Ok
12 Correct 10 ms 9720 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Ok
2 Correct 9 ms 9720 KB Ok
3 Correct 10 ms 9720 KB Ok
4 Correct 10 ms 9720 KB Ok
5 Correct 9 ms 9720 KB Ok
6 Correct 11 ms 9976 KB Ok
7 Correct 20 ms 11128 KB Ok
8 Correct 13 ms 10360 KB Ok
9 Correct 19 ms 11260 KB Ok
10 Correct 15 ms 10620 KB Ok

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Ok
2 Correct 10 ms 9748 KB Ok
3 Correct 9 ms 9848 KB Ok
4 Correct 8 ms 9720 KB Ok
5 Correct 8 ms 9720 KB Ok
6 Correct 8 ms 9848 KB Ok
7 Incorrect 8 ms 9720 KB there is incorrect sequence
8 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9720 KB Ok
2 Correct 9 ms 9820 KB Ok
3 Correct 10 ms 9720 KB Ok
4 Correct 9 ms 9720 KB Ok
5 Correct 9 ms 9852 KB Ok
6 Correct 141 ms 28620 KB Ok
7 Correct 130 ms 29420 KB Ok
8 Correct 233 ms 33908 KB Ok
9 Correct 165 ms 31208 KB Ok
10 Correct 93 ms 20592 KB Ok
11 Correct 162 ms 31696 KB Ok

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Ok
2 Correct 9 ms 9720 KB Ok
3 Correct 10 ms 9720 KB Ok
4 Correct 9 ms 9720 KB Ok
5 Correct 10 ms 9724 KB Ok
6 Correct 10 ms 9720 KB Ok
7 Correct 9 ms 9720 KB Ok
8 Correct 9 ms 9720 KB Ok
9 Correct 10 ms 9720 KB Ok
10 Correct 9 ms 9720 KB Ok
11 Correct 9 ms 9720 KB Ok
12 Correct 10 ms 9720 KB Ok
13 Correct 10 ms 9720 KB Ok
14 Correct 10 ms 9748 KB Ok
15 Correct 9 ms 9848 KB Ok
16 Correct 8 ms 9720 KB Ok
17 Correct 8 ms 9720 KB Ok
18 Correct 8 ms 9848 KB Ok
19 Incorrect 8 ms 9720 KB there is incorrect sequence
20 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Ok
2 Correct 9 ms 9720 KB Ok
3 Correct 10 ms 9720 KB Ok
4 Correct 9 ms 9720 KB Ok
5 Correct 10 ms 9724 KB Ok
6 Correct 10 ms 9720 KB Ok
7 Correct 9 ms 9720 KB Ok
8 Correct 9 ms 9720 KB Ok
9 Correct 10 ms 9720 KB Ok
10 Correct 9 ms 9720 KB Ok
11 Correct 9 ms 9720 KB Ok
12 Correct 10 ms 9720 KB Ok
13 Correct 10 ms 9720 KB Ok
14 Correct 9 ms 9720 KB Ok
15 Correct 10 ms 9720 KB Ok
16 Correct 10 ms 9720 KB Ok
17 Correct 9 ms 9720 KB Ok
18 Correct 11 ms 9976 KB Ok
19 Correct 20 ms 11128 KB Ok
20 Correct 13 ms 10360 KB Ok
21 Correct 19 ms 11260 KB Ok
22 Correct 15 ms 10620 KB Ok
23 Correct 10 ms 9720 KB Ok
24 Correct 10 ms 9748 KB Ok
25 Correct 9 ms 9848 KB Ok
26 Correct 8 ms 9720 KB Ok
27 Correct 8 ms 9720 KB Ok
28 Correct 8 ms 9848 KB Ok
29 Incorrect 8 ms 9720 KB there is incorrect sequence
30 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Ok
2 Correct 9 ms 9720 KB Ok
3 Correct 10 ms 9720 KB Ok
4 Correct 9 ms 9720 KB Ok
5 Correct 10 ms 9724 KB Ok
6 Correct 10 ms 9720 KB Ok
7 Correct 9 ms 9720 KB Ok
8 Correct 9 ms 9720 KB Ok
9 Correct 10 ms 9720 KB Ok
10 Correct 9 ms 9720 KB Ok
11 Correct 9 ms 9720 KB Ok
12 Correct 10 ms 9720 KB Ok
13 Correct 10 ms 9720 KB Ok
14 Correct 9 ms 9720 KB Ok
15 Correct 10 ms 9720 KB Ok
16 Correct 10 ms 9720 KB Ok
17 Correct 9 ms 9720 KB Ok
18 Correct 11 ms 9976 KB Ok
19 Correct 20 ms 11128 KB Ok
20 Correct 13 ms 10360 KB Ok
21 Correct 19 ms 11260 KB Ok
22 Correct 15 ms 10620 KB Ok
23 Correct 10 ms 9720 KB Ok
24 Correct 10 ms 9748 KB Ok
25 Correct 9 ms 9848 KB Ok
26 Correct 8 ms 9720 KB Ok
27 Correct 8 ms 9720 KB Ok
28 Correct 8 ms 9848 KB Ok
29 Incorrect 8 ms 9720 KB there is incorrect sequence
30 Halted 0 ms 0 KB -