# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
100367 |
2019-03-10T16:04:09 Z |
claudy |
Zalmoxis (BOI18_zalmoxis) |
C++14 |
|
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();
}
}
# |
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 |
# |
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 |