Submission #100368

#	Time	Username	Problem	Language	Result	Execution time	Memory
100368		claudy	Zalmoxis (BOI18_zalmoxis)	C++14	100 / 100	260 ms	33680 KiB

zalmoxis

# pragma GCC optimize("O3")
# include <bits/stdc++.h>
std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define rcg(s) cout << s;exit(0)
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define all(s) s.begin(),s.end()
# define sz(x) (int)((x).size())
//# define int ll
using namespace std;
int gcd(int a, int b)
{
    if(b) return gcd(b,a%b);
    return a;
}mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

stack<int>s;
int n,k,a[1 << 20];
vector<int>vec[1 << 20];

void f(int x)
{
	if(x == 0 || k == 0) cout << x << ' ';
	else
	{
		k--;
		f(x - 1);f(x - 1);
	}
}

int32_t main(){_
    //freopen("in","r",stdin);
	cin >> n >> k;
	for(int i = 1;i <= n;i++)
	{
		cin >> a[i];
	}
	s.push(29);
	s.push(29);
	for(int i = 1;i <= n;i++)
	{
		/*if(i == 5)
		{
			while(sz(s))
			{
				cout << s.top() << ' ';
				s.pop();
			}
			return 0;
		}*/
		int x = s.top();
		if(a[i] == x)
		{
			s.pop();
			continue;
		}
		else if(a[i] < x)
		{
			s.pop();
			for(int j = x - 1;j >= a[i];j--)
			{
				s.push(j);
			}
		}
		else
		{
			while(s.top() < a[i])
			{
				vec[i].pb(s.top());
				k--;
				s.pop();
			}
			int x = s.top();
			if(a[i] == x)
			{
				s.pop();
				continue;
			}
			else if(a[i] < x)
			{
				s.pop();
				for(int j = x - 1;j >= a[i];j--)
				{
					s.push(j);
				}
			}
		}
	}
	k -= sz(s);
	for(int i = 1;i <= n;i++)
	{
		for(auto it : vec[i])
		{
			f(it);
		}
		cout << a[i] << ' ';
	}
	while(sz(s))
	{
		auto it = s.top();
		f(it);
		s.pop();
	}
}

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