oj.uz

Submission #100365

# Submission time Handle Problem Language Result Execution time Memory
100365 2019-03-10T15:49:52 Z claudy Zalmoxis (BOI18_zalmoxis) C++14
45 / 100
 235 ms 59616 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);
				}
			}
		}
	}
	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 32632 KB Output is correct
2 Correct 173 ms 32456 KB Output is correct
3 Correct 181 ms 32632 KB Output is correct
4 Correct 168 ms 32648 KB Output is correct
5 Correct 226 ms 32532 KB Output is correct
6 Correct 188 ms 32500 KB Output is correct

Subtask #2
15.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 190 ms 32504 KB not a zalsequence
2 Runtime error 137 ms 59616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 141 ms 59512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 169 ms 32504 KB not a zalsequence
5 Incorrect 172 ms 32504 KB not a zalsequence
6 Incorrect 235 ms 32612 KB not a zalsequence
7 Incorrect 204 ms 32504 KB not a zalsequence
8 Incorrect 190 ms 32504 KB not a zalsequence
9 Incorrect 200 ms 35288 KB not a zalsequence
10 Incorrect 184 ms 31548 KB not a zalsequence
11 Incorrect 147 ms 33404 KB not a zalsequence
12 Correct 95 ms 27000 KB Output is correct
13 Correct 100 ms 27000 KB Output is correct
14 Correct 88 ms 27000 KB Output is correct