Submission #126581

#	Time	Username	Problem	Language	Result	Execution time	Memory
126581		miguel	Zalmoxis (BOI18_zalmoxis)	C++14	0 / 100	169 ms	8564 KiB

zalmoxis

#include<bits/stdc++.h>
using namespace std;
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define sz size()
#define x first
#define y second
#define pi pair <int, int>
#define pii pair <int, pi>
#define vi vector <int>
const ll mod = 1e9 + 7;
int n, k, cnt[31], cntmin[31], t[1000001];///min asta minimul necesar de adaugat, care dupa il manipulam cu shiretlikuri

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n>>k;
    for(int i=1; i<=n; i++){
        int x;
        cin>>x;
        t[i]=x;
        cnt[x]++;
    }
    //for(int i=0; i<=30; i++) cnta[i]=cnt[i];
    int pr=0;
    for(int i=0; i<=29; i++){
        if((cnt[i]+pr)%2) cntmin[i]++;
        pr=(cnt[i]+pr+cntmin[i])/2;
        //if(i>=25) cout<<i<<" "<<cnt[i]<<" "<<pr<<endl;
    }
    //for(int i=25; i<=30; i++) cout<<i<<" "<<cntmin[i]<<endl;
    int cur=0, ix=30;
    for(int i=0; i<=30; i++) cur+=cntmin[i];
    //cout<<cur<<endl;
    while(cur<k){
        int xd=min(k-cur, cntmin[ix]);
        if(cntmin[ix]){
            cntmin[ix-1]+=2*xd;
            cur+=xd;
            cntmin[ix]-=xd;
            //cout<<"xd";
        }
        //cout<<ix<<" "<<xd<<" "<<cur<<endl;
        ix--;
    }
    for(int i=1; i<=n; i++){
        cout<<t[i]<<" ";
        if(cntmin[t[i]]){
            cntmin[t[i]]--;
            cout<<t[i]<<" ";
        }
    }
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70