oj.uz

Submission #74097

# Submission time Handle Problem Language Result Execution time Memory
74097 2018-08-30T05:38:45 Z zscoder Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 278 ms 51684 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 24272 KB Output is correct
2 Correct 275 ms 26356 KB Output is correct
3 Correct 256 ms 28632 KB Output is correct
4 Correct 263 ms 30740 KB Output is correct
5 Correct 273 ms 32864 KB Output is correct
6 Correct 254 ms 34708 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 36760 KB Output is correct
2 Correct 250 ms 38800 KB Output is correct
3 Correct 258 ms 41056 KB Output is correct
4 Correct 278 ms 43128 KB Output is correct
5 Correct 260 ms 45160 KB Output is correct
6 Correct 256 ms 47156 KB Output is correct
7 Correct 265 ms 49340 KB Output is correct
8 Correct 260 ms 51392 KB Output is correct
9 Correct 233 ms 51684 KB Output is correct
10 Correct 176 ms 51684 KB Output is correct
11 Correct 200 ms 51684 KB Output is correct
12 Correct 132 ms 51684 KB Output is correct
13 Correct 151 ms 51684 KB Output is correct
14 Correct 132 ms 51684 KB Output is correct