Submission #1229966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229966		MuhammadSaram	Zalmoxis (BOI18_zalmoxis)	C++20	0 / 100	1102 ms	61516 KiB

zalmoxis

#include <bits/stdc++.h>

using namespace std;

#define dd double
#define all(v) v.begin(), v.end()

const int M = 31;
const dd eps = 0.000001;

vector<dd> ind[M];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);
	
	int n,k;
	cin>>n>>k;
	int a[n];
	for (int i=0;i<n;i++)
		cin>>a[i],ind[a[i]].push_back(i);
	for (int x=0;x<M;x++)
	{
		int m=ind[x].size();
		for (int ct=0;ct<m;ct++)
		{
			dd i=ind[x][ct];
			dd pr=0,nx=n;
			for (int y=x+1;y<M;y++)
			{
				int o=lower_bound(all(ind[y]),i)-begin(ind[y]);
				if (o) pr=max(pr,ind[y][o-1]);
				if (o<ind[y].size()) nx=min(nx,ind[y][o]);
			}
			int cnt=0;
			for (int y=0;y<x;y++)
			{
				int q=lower_bound(all(ind[y]),pr)-begin(ind[y]);
				int w=lower_bound(all(ind[y]),nx)-begin(ind[y]);
				cnt=cnt/2+q-w;
			}
			cnt/=2;
			if (cnt%2) k--,ind[x].push_back(i+eps);
		}
		sort(all(ind[x]));
	}
	vector<pair<dd,int>> v;
	for (int x=0;x<M;x++)
		for (auto i:ind[x])
			v.push_back({i,x});
	sort(all(v));
	for (auto [i,x]:v)
	{
		dd j=floor(i);
		vector<int> p={x};
		int cnt=0;
		if (j<i)
		{
			while (k && p.size())
			{
				int s=p.back();p.pop_back();
				if (!s)
				{
					cnt++;
					continue;
				}
				k--,p.push_back(s-1),p.push_back(s-1);
			}
		}
		for (int s:p) cout<<s<<' ';
		while (cnt--) cout<<0<<' ';
	}
	cout<<endl;
	
	return 0;
}

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