Submission #77889

#	Time	Username	Problem	Language	Result	Execution time	Memory
77889		antimirage	Nice sequence (IZhO18_sequence)	C++17	100 / 100	1393 ms	38824 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, deg[N], u[N], ans[N];

vector <int> vec, topo;

inline bool check (int len, bool fl = false)
{
    if (fl)
        topo.clear();

    memset(deg, 0, sizeof(deg));

    for (int i = 0; i <= len; i++)
    {
        if (i + n <= len)
            deg[i + n]++;
        if (i + m <= len)
            deg[i]++;
    }
    for (int i = 0; i <= len; i++)
    {
        if(!deg[i])
            vec.pb(i);
    }
    while (!vec.empty() )
    {
        int v = vec.back();
        vec.pop_back();

        if (v + n <= len && deg[v + n])
        {
            vec.pb(v + n);
            deg[v + n]--;
        }
        if (v - m >= 0 && deg[v - m])
        {
            vec.pb(v - m);
            deg[v - m]--;
        }
        if(fl)
            topo.pb(v);
    }
    for (int i = 0; i <= len; i++)
    {
        if (deg[i])
            return false;
    }
    return true;
}
main()
{
    cin >> tests;
    while (tests--)
    {
        scanf("%d%d", &n, &m);

        swap(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, 1);
        printf("%d\n", l);

        int pos = lower_bound ( all(topo), 0 ) - topo.begin();
        for (int i = 0; i <= l; i++)
            ans[topo[i]] = i - pos;

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

        printf("\n");
    }
}

Compilation message (stderr)

sequence.cpp:71:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
sequence.cpp: In function 'int main()':
sequence.cpp:76: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: 6 / 6
• Subtask 2: 9 / 9
• Subtask 3: 14 / 14
• Subtask 4: 15 / 15
• Subtask 5: 14 / 14
• Subtask 6: 18 / 18
• Subtask 7: 24 / 24