Submission #1314771

#TimeUsernameProblemLanguageResultExecution timeMemory
1314771arman.khachatryanGift (IZhO18_nicegift)C++20
19 / 100
470 ms30444 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
    int a, b;
    ll val;
};
int main() {
    int n, k;
    cin>>n>>k;
    pair<ll, int> a[n];
    bool bl=false;
    for(int i=0; i<n; i++){
        cin>>a[i].first;
        a[i].second=i+1;
        if(i>0 && a[i]!=a[i-1]){
            bl=true;
        }
    }
    if(bl){
        int g;
        for(int i=1; i<=k; i++){
            if(n%i==0 && k%i==0){
                g=i;
            }
        }
        if((n*a[0].first)%k!=0){
            cout<<-1;
            return 0;
        }
        cout<<n/g<<'\n';
        for(int i=0; i<n/g; i++){
            cout<<a[0].first*g/k<<" ";
            for(int j=0; j<k; j++){
                cout<<(i*g+j)%n+1LL<<" ";
            }
            cout<<'\n';
        }
        return 0;
    }
    if(n==2){
        if(a[0].first==a[1].first){
            cout<<a[0].first<<" "<<1<<" "<<2<<'\n';
        }else{
           cout<<-1<<'\n';
        }
        return 0;
    }
    sort(a, a+n, [&](pair<ll, int> x, pair<ll, int> y){
        return x.first<y.first;
    });
    int sum=0;
    for(int i=0; i<n-1; i++){
        sum+=a[i].first;
    }
    if(sum<a[n-1].first || (sum+a[n-1].first)%2==1){
        cout<<-1;
    }else{
        sum-=a[n-1].first;
        vector<node> v;
        while(sum>0){
            if(sum>=2*a[n-3].first){
                sum-=2*a[n-3].first;
                v.push_back({a[n-2].second, a[n-3].second, a[n-3].first});
                a[n-2].first-=a[n-3].first;
                a[n-3].first=0;
            }else{
                v.push_back({a[n-2].second, a[n-3].second, sum/2});
                a[n-2].first-=sum/2;
                a[n-3].first-=sum/2;
                break;
            }
            for(int i=n-3; i>0; i--){
                swap(a[i], a[i-1]);
            }
            for(int i=n-2; i>0; i--){
                if(a[i].first>=a[i-1].first){
                    break;
                }
                swap(a[i], a[i-1]);
            }
        }
        for(int i=0; i<n-1; i++){
            if(a[i].first>0){
                v.push_back({a[n-1].second, a[i].second, a[i].first});
            }
        }
        cout<<v.size()<<'\n';
        for(auto& it : v){
            cout<<it.val<<" "<<it.a<<" "<<it.b<<'\n';
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...