Submission #1128674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128674		_callmelucian	Gift (IZhO18_nicegift)	C++17	0 / 100	2091 ms	31764 KiB

nicegift

#include <bits/stdc++.h>
using namespace std;

#define int long long

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

struct increase {
    ll amount; vector<int> vec;
    increase (ll a, vector<int> cur) : amount(a), vec(cur) {}

    void push (int cur) { vec.push_back(cur); }
};
vector<increase> res;

const int mn = 1e6 + 6;
int cur[mn], a[mn], n, k;

void print() {
    vector<ll> b(n + 1);
    cout << res.size() << "\n";
    for (increase &item : res) {
        cout << item.amount << " ";
        for (int u : item.vec) cout << u << " ";
        cout << "\n";

        for (int u : item.vec) b[u] += item.amount;
    }

    for (int i = 1; i <= n; i++) {
        if (a[i] != b[i]) return cerr << "WA\n", void();
    }
}

void operation (vector<int> poses, ll mult) {
    // increase all of this positions by k / gcd(k, poses.size()) * mult
    for (int u : poses) cur[u] = 0;
    for (int it = poses.size() / __gcd(k, (int)poses.size()); it; it--) {
        sort(all(poses), [&] (int a, int b) { return cur[a] < cur[b]; });
        vector<int> tmp(poses.begin(), poses.begin() + k);
        for (int u : tmp) cur[u] += mult;
        res.emplace_back(mult, tmp);
    }
}

namespace allSame {
    int only;

    void solve() {
        int base = k / __gcd(k, n);
        if (only % base) return cout << -1, void();
        vector<int> vec(n);
        iota(all(vec), 1);
        operation(vec, only / base);
        return print(), void();
    }

    bool check() {
        only = *min_element(a + 1, a + 1 + n);
        return (only == *max_element(a + 1, a + 1 + n));
    }
};

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];

    if (allSame::check()) return allSame::solve(), 0;

    return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 51