Submission #77367

#	Time	Username	Problem	Language	Result	Execution time	Memory
77367		antimirage	Nice sequence (IZhO18_sequence)	C++17	0 / 100	1178 ms	35972 KiB

sequence

#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 (stderr)

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
• Subtask 2: 0 / 9
• Subtask 3: 0 / 14
• Subtask 4: 0 / 15
• Subtask 5: 0 / 14
• Subtask 6: 0 / 18
• Subtask 7: 0 / 24