oj.uz

Submission #100367

# Submission time Handle Problem Language Result Execution time Memory
100367 2019-03-10T16:04:09 Z claudy Zalmoxis (BOI18_zalmoxis) C++14
45 / 100
 1000 ms 263168 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(i);
				}
			}
		}
	}
	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 165 ms 31056 KB Output is correct
2 Correct 180 ms 30968 KB Output is correct
3 Correct 191 ms 31224 KB Output is correct
4 Correct 169 ms 30968 KB Output is correct
5 Correct 260 ms 30980 KB Output is correct
6 Correct 243 ms 30968 KB Output is correct

Subtask #2
15.0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 125 ms 57720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 353 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 359 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Execution timed out 1074 ms 57720 KB Time limit exceeded
5 Execution timed out 1074 ms 53728 KB Time limit exceeded
6 Execution timed out 1076 ms 58744 KB Time limit exceeded
7 Execution timed out 1079 ms 54120 KB Time limit exceeded
8 Execution timed out 1076 ms 54540 KB Time limit exceeded
9 Runtime error 391 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 338 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 300 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Correct 100 ms 26872 KB Output is correct
13 Correct 104 ms 26872 KB Output is correct
14 Correct 92 ms 27000 KB Output is correct