| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1101154 |
2024-10-15T16:49:59 Z |
MateiKing80 |
Swap (BOI16_swap) |
C++14 |
|
510 ms |
233896 KB |
#include <bits/stdc++.h>
using namespace std;
int a[200002];
bool nevoie[200002][18][2];
vector<int> dp[200002][18][2], sus, sus2;
void mrg(vector<int> &ret, vector<int> &l, vector<int> &r)
{
for(int i = 0, j = 1; i < l.size(); i += j, j <<= 1)
{
for(int k = i; k < i + j && k < l.size(); k ++)
ret.push_back(l[k]);
for(int k = i; k < i + j && k < r.size(); k ++)
ret.push_back(r[k]);
}
}
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i ++)
cin >> a[i];
nevoie[1][0][1] = 1;
for(int nod = 1; nod <= n / 2; nod ++)
for(int i = 0; nod >> i; i ++)
for(int j :{0, 1})
{
if(!nevoie[nod][i][j])
continue;
int mn = min({a[((nod >> i + 1) << 1) + j], a[2 * nod], a[2 * nod + 1]});
if(mn == a[((nod >> i + 1) << 1) + j])
nevoie[2 * nod][0][0] = nevoie[2 * nod + 1][0][1] = 1;
else if(mn == a[2 * nod])
nevoie[2 * nod][i + 1][j] = nevoie[2 * nod + 1][0][1] = 1;
else
{
nevoie[2 * nod][0][0] = nevoie[2 * nod][i + 1][j] = 1;
nevoie[2 * nod + 1][0][0] = nevoie[2 * nod + 1][i + 1][j] = 1;
}
}
for(int nod = n; nod; nod --)
{
for(int i = 0; nod >> i; i ++)
for(int j = 0; j < 2; j ++)
{
if(!nevoie[nod][i][j])
continue;
int p = ((nod >> i + 1) << 1) + j;
if(2 * nod > n)
dp[nod][i][j] = {a[p]};
else if(2 * nod == n)
dp[nod][i][j] = {min(a[p], a[2 * nod]), max(a[p], a[2 * nod])};
else if(a[2 * nod + 1] < min(a[p], a[2 * nod]))
{
sus = sus2 = {a[2 * nod + 1]};
mrg(sus, dp[2 * nod][0][0], dp[2 * nod + 1][i + 1][j]);
mrg(sus2, dp[2 * nod][i + 1][j], dp[2 * nod + 1][0][0]);
dp[nod][i][j] = min(sus, sus2);
}
else
{
dp[nod][i][j] = {min(a[p], a[2 * nod])};
if(a[p] < a[2 * nod])
mrg(dp[nod][i][j], dp[2 * nod][0][0], dp[2 * nod + 1][0][1]);
else
mrg(dp[nod][i][j], dp[2 * nod][i + 1][j], dp[2 * nod + 1][0][1]);
}
}
if(2 * nod < n)
for(int i = 0; 2 * nod >> i; i ++)
for(int j = 0; j < 2; j ++)
{
vector<int>().swap(dp[2 * nod][i][j]);
vector<int>().swap(dp[2 * nod + 1][i][j]);
}
}
for(int i : dp[1][0][1])
cout << i << " ";
return 0;
}
Compilation message
swap.cpp: In function 'void mrg(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
swap.cpp:11:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | for(int i = 0, j = 1; i < l.size(); i += j, j <<= 1)
| ~~^~~~~~~~~~
swap.cpp:13:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | for(int k = i; k < i + j && k < l.size(); k ++)
| ~~^~~~~~~~~~
swap.cpp:15:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | for(int k = i; k < i + j && k < r.size(); k ++)
| ~~^~~~~~~~~~
swap.cpp: In function 'int main()':
swap.cpp:33:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
33 | int mn = min({a[((nod >> i + 1) << 1) + j], a[2 * nod], a[2 * nod + 1]});
| ~~^~~
swap.cpp:34:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
34 | if(mn == a[((nod >> i + 1) << 1) + j])
| ~~^~~
swap.cpp:51:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
51 | int p = ((nod >> i + 1) << 1) + j;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
172876 KB |
Output is correct |
| 2 |
Correct |
35 ms |
172880 KB |
Output is correct |
| 3 |
Correct |
30 ms |
172976 KB |
Output is correct |
| 4 |
Correct |
30 ms |
172880 KB |
Output is correct |
| 5 |
Correct |
32 ms |
172936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
172876 KB |
Output is correct |
| 2 |
Correct |
35 ms |
172880 KB |
Output is correct |
| 3 |
Correct |
30 ms |
172976 KB |
Output is correct |
| 4 |
Correct |
30 ms |
172880 KB |
Output is correct |
| 5 |
Correct |
32 ms |
172936 KB |
Output is correct |
| 6 |
Correct |
29 ms |
172848 KB |
Output is correct |
| 7 |
Correct |
30 ms |
172884 KB |
Output is correct |
| 8 |
Correct |
29 ms |
172884 KB |
Output is correct |
| 9 |
Correct |
30 ms |
172984 KB |
Output is correct |
| 10 |
Correct |
29 ms |
172884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
172876 KB |
Output is correct |
| 2 |
Correct |
35 ms |
172880 KB |
Output is correct |
| 3 |
Correct |
30 ms |
172976 KB |
Output is correct |
| 4 |
Correct |
30 ms |
172880 KB |
Output is correct |
| 5 |
Correct |
32 ms |
172936 KB |
Output is correct |
| 6 |
Correct |
29 ms |
172848 KB |
Output is correct |
| 7 |
Correct |
30 ms |
172884 KB |
Output is correct |
| 8 |
Correct |
29 ms |
172884 KB |
Output is correct |
| 9 |
Correct |
30 ms |
172984 KB |
Output is correct |
| 10 |
Correct |
29 ms |
172884 KB |
Output is correct |
| 11 |
Correct |
32 ms |
172876 KB |
Output is correct |
| 12 |
Correct |
30 ms |
172884 KB |
Output is correct |
| 13 |
Correct |
30 ms |
172884 KB |
Output is correct |
| 14 |
Correct |
34 ms |
173140 KB |
Output is correct |
| 15 |
Correct |
31 ms |
172992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
172876 KB |
Output is correct |
| 2 |
Correct |
35 ms |
172880 KB |
Output is correct |
| 3 |
Correct |
30 ms |
172976 KB |
Output is correct |
| 4 |
Correct |
30 ms |
172880 KB |
Output is correct |
| 5 |
Correct |
32 ms |
172936 KB |
Output is correct |
| 6 |
Correct |
29 ms |
172848 KB |
Output is correct |
| 7 |
Correct |
30 ms |
172884 KB |
Output is correct |
| 8 |
Correct |
29 ms |
172884 KB |
Output is correct |
| 9 |
Correct |
30 ms |
172984 KB |
Output is correct |
| 10 |
Correct |
29 ms |
172884 KB |
Output is correct |
| 11 |
Correct |
32 ms |
172876 KB |
Output is correct |
| 12 |
Correct |
30 ms |
172884 KB |
Output is correct |
| 13 |
Correct |
30 ms |
172884 KB |
Output is correct |
| 14 |
Correct |
34 ms |
173140 KB |
Output is correct |
| 15 |
Correct |
31 ms |
172992 KB |
Output is correct |
| 16 |
Correct |
73 ms |
177616 KB |
Output is correct |
| 17 |
Correct |
77 ms |
177608 KB |
Output is correct |
| 18 |
Correct |
76 ms |
177740 KB |
Output is correct |
| 19 |
Correct |
124 ms |
187468 KB |
Output is correct |
| 20 |
Correct |
127 ms |
187420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
172876 KB |
Output is correct |
| 2 |
Correct |
35 ms |
172880 KB |
Output is correct |
| 3 |
Correct |
30 ms |
172976 KB |
Output is correct |
| 4 |
Correct |
30 ms |
172880 KB |
Output is correct |
| 5 |
Correct |
32 ms |
172936 KB |
Output is correct |
| 6 |
Correct |
29 ms |
172848 KB |
Output is correct |
| 7 |
Correct |
30 ms |
172884 KB |
Output is correct |
| 8 |
Correct |
29 ms |
172884 KB |
Output is correct |
| 9 |
Correct |
30 ms |
172984 KB |
Output is correct |
| 10 |
Correct |
29 ms |
172884 KB |
Output is correct |
| 11 |
Correct |
32 ms |
172876 KB |
Output is correct |
| 12 |
Correct |
30 ms |
172884 KB |
Output is correct |
| 13 |
Correct |
30 ms |
172884 KB |
Output is correct |
| 14 |
Correct |
34 ms |
173140 KB |
Output is correct |
| 15 |
Correct |
31 ms |
172992 KB |
Output is correct |
| 16 |
Correct |
73 ms |
177616 KB |
Output is correct |
| 17 |
Correct |
77 ms |
177608 KB |
Output is correct |
| 18 |
Correct |
76 ms |
177740 KB |
Output is correct |
| 19 |
Correct |
124 ms |
187468 KB |
Output is correct |
| 20 |
Correct |
127 ms |
187420 KB |
Output is correct |
| 21 |
Correct |
217 ms |
188236 KB |
Output is correct |
| 22 |
Correct |
251 ms |
188232 KB |
Output is correct |
| 23 |
Correct |
230 ms |
187468 KB |
Output is correct |
| 24 |
Correct |
472 ms |
233804 KB |
Output is correct |
| 25 |
Correct |
510 ms |
233896 KB |
Output is correct |
