| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 98337 |
2019-02-22T14:43:32 Z |
Kastanda |
Swap (BOI16_swap) |
C++11 |
|
33 ms |
25464 KB |
// * Sigh *
#include<bits/stdc++.h>
using namespace std;
const int N = 400005;
int n, A[N], M[N], H[N];
vector < int > S[N];
inline bool CMP(int i, int j)
{
return (A[i] > A[j]);
}
inline bool Sub(int i, int j)
{
return ((i >> (H[i] - H[j])) == j);
}
inline bool Check(int i, int val)
{
return (Sub(i, M[val]));
}
int main()
{
scanf("%d", &n);
memset(A, 63, sizeof(A));
for (int i = 1; i <= n; i++)
scanf("%d", &A[i]),
S[i].push_back(i);
for (int i = 1; i < N; i++)
H[i] = H[i >> 1] + 1;
for (int i = 1; i <= n; i++)
{
int lc = i << 1, rc = lc ^ 1;
sort(S[i].begin(), S[i].end(), CMP);
while (!Check(i, A[S[i].back()]))
S[i].pop_back();
printf("%d ", min({A[S[i].back()], A[lc], A[rc]}));
M[min({A[S[i].back()], A[lc], A[rc]})] = n + 1;
if (A[S[i].back()] < min(A[lc], A[rc]))
{
int id = S[i].back(), nw = i;
if (!Sub(i, id))
{
int p = id >> 1;
for (int a : S[p])
M[a] = max(M[a], id);
S[p].clear();
id ^= 1;
}
while (nw > id)
{
int p = nw >> 1;
for (int a : S[p])
M[a] = max(M[a], nw);
M[A[nw^1]] = min(M[A[nw^1]], nw ^ 1);
S[p].clear(); nw >>= 1;
}
}
else if (A[lc] < A[rc])
S[lc] = S[i];
else
{
S[lc] = S[rc] = S[i];
S[lc].push_back(lc);
S[rc].push_back(lc);
}
}
return 0;
}
Compilation message
swap.cpp: In function 'int main()':
swap.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
swap.cpp:24:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &A[i]),
~~~~~~~~~~~~~~~~~~^~
S[i].push_back(i);
~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
33 ms |
25464 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
33 ms |
25464 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
33 ms |
25464 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
33 ms |
25464 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
33 ms |
25464 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
