Submission #74199

#	Time	Username	Problem	Language	Result	Execution time	Memory
74199		jiaqing23	Zalmoxis (BOI18_zalmoxis)	C++14	100 / 100	924 ms	81000 KiB

zalmoxis

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<int,int> pi;
typedef vector<ll> vi;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;
typedef pair<int,pair<int,int> > tri;

int n, k;
int a[1000050];
set<pi> s;
//set<int> pos;
multiset<int> s2;
vector<int> add[1000050];
int addnum = 0;
int need;
int cnt[35];
int nxt[1000050];

int tem = 0;

void split(int k1){
    assert(k1>=0);
    for(int i = 0; i < 35; i++) cnt[i] = 0;
    cnt[k1] = 1;
    //cout<<"SPLIT "<<k1<<endl;
    int j = 0;
    while(need){
        //if(need>-10 && need < 10000)cout<<"NEED : "<<need<<endl;
        if(k1==0) break;
        if(cnt[k1]>0){

            cnt[k1]--;
            cnt[k1-1] +=2;
            need --;
        }
        else k1--;

    }
    for(int i = 0; i <= 30; i++){
        for(int j = 0; j < cnt[i]; j++){
            cout << i << ' ';
            //tem++;
        }
    }
}

int main()
{
	//ios_base::sync_with_stdio(0); cin.tie(0);
	//freopen("8z.in","r",stdin);

	cin >> n >> k;
	for(int i = 0; i < n; i++){
        scanf("%d",&a[i]);
        s.insert(mp(a[i],i));
        //assert(a[i] == 0);
       //pos.insert(i);
        if(i!=n-1) nxt[i] = i+1;
        else nxt[i] = -1;
	}

	while(1){
        auto it = s.begin();
        pi p = *it;
        //cout<<p.fi<<endl;
        if(s.size()==1){
            if(p.fi==30) break;
            else{
                for(int i = p.fi; i <= 29; i++){
                    add[p.se].pb(i);
                    //assert(i>0);
                    addnum++;
                }
                s.erase(it);
                s.insert(mp(30,p.se));
            }
        }
        else{
            auto it2 = ++it;
            pi next = *it2;
            it--;
            if(p.fi == next.fi && nxt[p.se] == next.se){
                s.erase(it2);
              //  pos.erase(next.se);
                nxt[p.se] = nxt[next.se];
                s.erase(it);
                s.insert(mp(p.fi+1, p.se));
            }
            else{
                add[p.se].pb(p.fi);
                //cout<<p.fi<<endl;
                //assert(p.fi>0);
                addnum ++;
                s.erase(it);
                s.insert(mp(p.fi+1, p.se));
            }
        }


	}

    need = k - addnum;
    for(int i = 0; i < n; i++){
        for(int j = add[i].size()-1; j >= 0; j--){
            assert(add[i][j] >= 0);
            if(need > 0) split(add[i][j]);
            else{
                printf("%d ",add[i][j]);
                //tem ++;
            }
        }
        printf("%d ",a[i]);
        //tem++;
        //cout<<"I: "<< i << endl;
    }
    //cout<<tem;
	return 0;
}

Compilation message (stderr)

zalmoxis.cpp: In function 'void split(int)':
zalmoxis.cpp:42:9: warning: unused variable 'j' [-Wunused-variable]
     int j = 0;
         ^
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i]);
         ~~~~~^~~~~~~~~~~~

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