Submission #74097

#	Time	Username	Problem	Language	Result	Execution time	Memory
74097		zscoder	Zalmoxis (BOI18_zalmoxis)	C++17	100 / 100	278 ms	51684 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
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int a[1111111];

void fix(vector<int> &S)
{
	while(S.size()>=2&&S[int(S.size())-2]==S[int(S.size())-1])
	{
		S.pop_back(); S.back()++;
	}
}

int cnt[33];

void partition(int v, vi &res, int siz)
{
	cnt[v]++; int fr=v;
	for(int i=0;i<siz;i++)
	{
		while(cnt[fr]==0) fr--;
		cnt[fr]--; cnt[fr-1]++; cnt[fr-1]++;
	}
	for(int i=0;i<31;i++)
	{
		for(int j=0;j<cnt[i];j++) res.pb(i);
	}
}

int main()
{
	vector<ii> ans;
	int n,k; scanf("%d %d",&n,&k);
	for(int i=0;i<n;i++)
	{
		scanf("%d",a+i);
	}
	a[n]=30;
	//first do a less than k solution
	vector<int> S;
	int ex=-1;
	for(int i=0;i<=n;i++)
	{
		int cur = a[i];
		while(!S.empty()&&S.back()==cur)
		{
			S.pop_back(); cur++;
		}
		while(!S.empty()&&cur>S.back())
		{
			S.pb(S.back()); ex=ans.size(); ans.pb(mp(S.back(), 1)); 
			fix(S);
		}
		if(i<n) ans.pb(mp(a[i],0));
		S.pb(cur); fix(S);
		/*
		for(int s:S)
		{
			cerr<<s<<' ';
		}
		cerr<<'\n';
		for(ii s:ans)
		{
			cerr<<s.fi<<' ';
		}
		cerr<<'\n';
		cerr<<'\n';
		*/
	}
	vi res;
	for(int i=0;i<ex;i++) res.pb(ans[i].fi);
	int cnt = n+k-int(ans.size());
	partition(ans[ex].fi, res, cnt);
	for(int i=ex+1;i<ans.size();i++) res.pb(ans[i].fi);
	for(int i=0;i<res.size();i++)
	{
		printf("%d",res[i]);
		if(i+1<res.size()) printf(" ");
	}
	printf("\n");
}	

Compilation message (stderr)

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:89:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=ex+1;i<ans.size();i++) res.pb(ans[i].fi);
                 ~^~~~~~~~~~~
zalmoxis.cpp:90:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<res.size();i++)
              ~^~~~~~~~~~~
zalmoxis.cpp:93:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i+1<res.size()) printf(" ");
      ~~~^~~~~~~~~~~
zalmoxis.cpp:48:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n,k; scanf("%d %d",&n,&k);
           ~~~~~^~~~~~~~~~~~~~~
zalmoxis.cpp:51:8: 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