oj.uz

Submission #100309

# Submission time Handle Problem Language Result Execution time Memory
100309 2019-03-10T11:05:20 Z claudy Zalmoxis (BOI18_zalmoxis) C++14
0 / 100
 232 ms 57948 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 i = x - 1;i >= a[i];i--)
				{
					s.push(i);
				}
			}
		}
	}
	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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 155 ms 30972 KB Expected EOF
2 Incorrect 176 ms 31068 KB Expected EOF
3 Incorrect 190 ms 30968 KB Expected EOF
4 Incorrect 170 ms 30968 KB Expected EOF
5 Incorrect 201 ms 30968 KB Expected EOF
6 Incorrect 232 ms 31024 KB Expected EOF

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 193 ms 31072 KB Expected EOF
2 Runtime error 132 ms 57948 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 125 ms 57904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 186 ms 30988 KB Expected EOF
5 Incorrect 159 ms 30968 KB Expected EOF
6 Incorrect 164 ms 31096 KB Expected EOF
7 Incorrect 161 ms 30968 KB Expected EOF
8 Incorrect 172 ms 30968 KB Expected EOF
9 Incorrect 156 ms 33656 KB Expected EOF
10 Incorrect 137 ms 30712 KB Expected EOF
11 Incorrect 154 ms 32376 KB Expected EOF
12 Incorrect 96 ms 26940 KB Expected EOF
13 Incorrect 92 ms 26872 KB Expected EOF
14 Incorrect 90 ms 27100 KB Expected EOF