oj.uz

Submission #77367

# Submission time Handle Problem Language Result Execution time Memory
77367 2018-09-26T15:35:29 Z antimirage Nice sequence (IZhO18_sequence) C++17
0 / 100
 1178 ms 35972 KB 
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <utility>
#include <memory.h>
#include <set>
#include <queue>
#include <map>

#define fr first
#define sc second
#define mk make_pair
#define pb emplace_back
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 1e6 + 5;

int n, m, tests, u[N], ans[N], root;

vector < vector <int> > g;

bool fl;

void dfs (int v, int p = 0)
{
    if (fl) return;

    u[v] = 1;

    for (auto to : g[v])
    {
        if (u[to] == 0)
            dfs(to, v);
        else if (u[to] == 1)
        {
            fl = true;
            return ;
        }
    }
    u[v] = 2;
}
inline bool check (int len)
{
    memset(u, 0, sizeof(u));
    fl = false;

    g.clear();
    g.resize(len + 1);
    for (int i = 0; i < len; i++)
    {
        if (i + n <= len)
            g[i].pb(i + n);
        if (i + m <= len)
            g[i + m].pb(i);
    }
    for (int i = 0; i <= len; i++)
    {
        if (u[i]) continue;
        root = i;
        dfs(i);
        if (fl) return false;
    }
    return true;
}
void calc (int v)
{
    u[v] = 1;

    for (auto to : g[v])
    {
        if (u[to] == 0)
            calc(to);

        ans[v] = max(ans[v], ans[to] + 1);
    }
}
main()
{
    cin >> tests;
    while (tests--)
    {
        scanf("%d%d", &n, &m);
        int l = 0, r = 1e6;

        while (r - l > 1)
        {
            int md = (l + r) >> 1;
            if ( check(md) )
                l = md;
            else
                r = md;
        }
        check(l);
        printf("%d\n", l);

        memset(u, 0, sizeof(u));
        memset(ans, 0, sizeof(ans));

        calc(root);

        for (int i = 1; i <= l; i++)
            printf("%d ", ans[i] - ans[i - 1]);

        printf("\n");
    }
}

Compilation message

sequence.cpp:82:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
sequence.cpp: In function 'int main()':
sequence.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &n, &m);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1086 ms 35644 KB Ok
2 Incorrect 1060 ms 35644 KB All the numbers must be nonzero
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1069 ms 35644 KB All the numbers must be nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 35644 KB Ok
2 Correct 1178 ms 35792 KB Ok
3 Incorrect 1061 ms 35924 KB All the numbers must be nonzero
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

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

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1086 ms 35644 KB Ok
2 Incorrect 1060 ms 35644 KB All the numbers must be nonzero
3 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1086 ms 35644 KB Ok
2 Incorrect 1060 ms 35644 KB All the numbers must be nonzero
3 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1086 ms 35644 KB Ok
2 Incorrect 1060 ms 35644 KB All the numbers must be nonzero
3 Halted 0 ms 0 KB -