Tikut

input/code.cpp: In function 'void sub1(vl&, ll, ll)':
input/code.cpp:48:26: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   48 |             if (v.size() <= h)
      |                 ~~~~~~~~~^~~~
input/code.cpp: In function 'int main()':
input/code.cpp:89:45: warning: unused variable 'mn' [-Wunused-variable]
   89 |     ll n, m, i, j, k, a, b, r, t, f = 0, c, mn, S = 0;
      |                                             ^~
input/code.cpp:191:21: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
  191 |         cout << a - b << " ";
      |                     ^
input/code.cpp:191:21: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pl;
typedef vector <pl> vpl;
#define fi first
#define se second
#define mp make_pair

#define outp(a) for(auto x:a) cerr << x << " "; cerr << " <--\n";
const ll inf = 1e18;

ll cal(vl &x, vl &v)
{
    ll i, j, mn, mx, cmn, cmx, c;
    mn = inf;
    mx = -inf;
    for(i = v.size()-1, j = x.size() - 1; i >= 0; i--, j--)
    {
        c = v[i] + 1;
        cmn = x[j] / c;
        if (cmn == 0) return inf;
        cmx = (x[j] + c - 1) / c;
        mn = min(mn, cmn);
        mx = max(mx, cmx);
    }
    for(; j >= 0; j--)
    {
        mn = min(mn, x[j]);
        mx = max(mx, x[j]);
    }
    return mx - mn;
}


void sub1(vl &x, ll n, ll m)
{
    ll k, h, ans;
    // cin >> k >> s;
    h = min(m, n);
    for(k = 1; k <= m; k++)
    {
        vl v(k, 1);
        ans = x[n-1];
        while(v.size() >= 1)
        {
            if (v.size() <= h)
            {
                // outp(v);
                ans = min(ans, cal(x, v));
            }
            if (v.size() == 1) break;
            ll j = v.size()-1, i = v.size()-2;
            if ((v[i]+1)*3 <= v[i]+v[j])
            {
                ll m, t = v[j];
                m = v[j] = ++v[i];
                t -= 1 + m;
                while(t >= 2*m)
                {
                    v.push_back(m);
                    t -= m;
                }
                v.push_back(t);
            }
            else if (v[i]+1 < v[j])
            {
                v[i]++, v[j]--;
            }
            else
            {
                v[i] += v[j];
                v.pop_back();
            }
        }
        cout << ans << " ";
    }
    cout << "\n";
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    multiset <ll> s;
    ll n, m, i, j, k, a, b, r, t, f = 0, c, mn, S = 0;
    vpl ap;

    cin >> n >> m;
    vl x(n);
    for(i = 0; i < n; i++)
    {
        cin >> x[i];
        S += x[i];
    }
    sort(x.begin(), x.end());

    if (m <= 10)
    {
        sub1(x, n, m);
        return 0;
    }

//    ap.push_back({x[0], 1});
//    mn = x[0];
//    for(i = 1; i < n; i++)
//    {
//        if(x[i] == x[i-1])
//            ap.back().se++;
//        else
//            ap.push_back({x[i], 1});
//    }

    for(i = 0; i < n; i++)
    {
        s.insert(x[i]);
    }
    t = m;
    for(k = 1; k <= t; k++)
    {
        if(s.size() == 1)
        {
            a = *s.begin();
            cout << (a % (k + 1) != 0) << " ";
            continue;
        }
        //cerr << k << ": ";
        m = k - f;
        while(m)
        {
            //for(auto x : s)
                //cerr << x << " ";
            //cerr << "\n";
            //cerr << "size: " << s.size() << "\n";
            //cerr << a << " " << b << "\n";
            auto it = s.end(); it--; a = *it;
            b = *s.begin();
            if(a == b)
            {
                c = s.size();
                a = a / (m / c + 1) + (a % (m / c + 1) != 0);
                b = b / (m / c + (m % c != 0) + 1);
                m = 0;
            }
            else
            {
                c = 0;
                //cerr << a << "!!!!!";
                while(*it == a)
                {
                    it--;
                    c++;
                }
                b = *it;
                if(m >= (a / b) * c)
                {
                    m -= (a / b) * c;
                    f += (a / b) * c;
                    it++;
                    s.erase(it, s.end());
                    //cerr << "*1";
                    i = a / b + 1;
                    r = a % i;
                    while(c--)
                    {
                        for(j = 1; j <= r; j++)
                            s.insert(a / i + 1);
                        for(j = r + 1; j <= i; j++)
                            s.insert(a / i);
                    }
                    it = s.end();
                    it--; a = *it;
                    it = s.begin(); b = *it;
                    //cerr << ": " << a << " " << b << "\n";
                }
                else
                {
                    //cerr << "*2";
                    i = b;
                    b = min(a / (m / c + (m % c != 0) + 1), *s.begin());
                    a = max(i, a / (m / c + 1) + ((a % (m / c + 1)) != 0));
                    m = 0;
                    //cerr << ": " << a << " " << b << "\n";
                }
            }
        }
        //cerr << a << " " << b << ": ";
        cout << a - b << " ";
    }
    //for(auto x : s)
        //cerr << x << " ";

    return 0;
}

Test 1

Group: 1, 3, 4, 5, 6

Verdict: ACCEPTED

Test 2

Group: 1, 4, 5, 6

Verdict: ACCEPTED

Test 3

Group: 1, 4, 5, 6

Verdict: ACCEPTED

Test 4

Group: 1, 4, 5, 6

Verdict: ACCEPTED

Test 5

Group: 2, 5, 6

Verdict: ACCEPTED

Test 6

Group: 2, 5, 6

Verdict: ACCEPTED

Test 7

Group: 3, 5, 6

Verdict: ACCEPTED

Test 8

Group: 3, 5, 6

Verdict: ACCEPTED

Test 9

Group: 3, 5, 6

Verdict: ACCEPTED

Test 10

Group: 3, 5, 6

Verdict: ACCEPTED

Test 11

Group: 3, 5, 6

Verdict: ACCEPTED

Test 12

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 13

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 14

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 15

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 16

Group: 5, 6

Verdict: WRONG ANSWER

Test 17

Group: 5, 6

Verdict: WRONG ANSWER

Test 18

Group: 5, 6

Verdict: WRONG ANSWER

Test 19

Group: 5, 6

Verdict: WRONG ANSWER

Test 20

Group: 6

Verdict: WRONG ANSWER

Test 21

Group: 6

Verdict: WRONG ANSWER

Test 22

Group: 6

Verdict: WRONG ANSWER