oj.uz

Submission #100368

# Submission time Handle Problem Language Result Execution time Memory
100368 2019-03-10T16:04:45 Z claudy Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 260 ms 33680 KB 
# 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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 30968 KB Output is correct
2 Correct 158 ms 30968 KB Output is correct
3 Correct 162 ms 30968 KB Output is correct
4 Correct 167 ms 30968 KB Output is correct
5 Correct 209 ms 30968 KB Output is correct
6 Correct 164 ms 30840 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 31096 KB Output is correct
2 Correct 189 ms 31352 KB Output is correct
3 Correct 179 ms 31352 KB Output is correct
4 Correct 170 ms 31096 KB Output is correct
5 Correct 172 ms 31108 KB Output is correct
6 Correct 174 ms 30968 KB Output is correct
7 Correct 260 ms 30940 KB Output is correct
8 Correct 173 ms 30968 KB Output is correct
9 Correct 206 ms 33680 KB Output is correct
10 Correct 142 ms 30960 KB Output is correct
11 Correct 148 ms 32576 KB Output is correct
12 Correct 143 ms 27112 KB Output is correct
13 Correct 104 ms 26984 KB Output is correct
14 Correct 100 ms 27000 KB Output is correct