| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 573425 |
2022-06-06T15:15:38 Z |
Tien_Noob |
Swap (BOI16_swap) |
C++17 |
|
1 ms |
1876 KB |
//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 4e5 + 1;
int a[N + 1], dp[N + 1], n;
int get(int u)
{
if (dp[u] == 0)
{
return a[u];
}
if (u & 1)
{
if (dp[u - 1] == 0)
{
return a[u/2];
}
else if (dp[u - 1] == 1)
{
return a[u - 1];
}
else if (dp[u - 1] == 2)
{
return min(get(u/2), a[u - 1]);
}
}
else
{
if (dp[u] == 1)
{
return get(u/2);
}
else
{
return min(get(u/2), a[u]);
}
}
}
void recolor(int u, int x)
{
if (dp[u] == 0)
{
return ;
}
if (u & 1)
{
if (dp[u - 1] == 0)
{
recolor(u/2, x);
}
else if (dp[u - 1] == 1)
{
return ;
}
else
{
if (a[u - 1] == x)
{
dp[u - 1] = 1;
return ;
}
dp[u - 1] = 0;
recolor(u/2, x);
}
}
else
{
if (dp[u] == 2)
{
if (a[u] == x)
{
dp[u] = 0;
return ;
}
dp[u] = 1;
}
recolor(u/2, x);
}
}
void read()
{
cin >> n;
memset(a, 0x3f, sizeof(a));
for (int i = 1; i <= n; ++ i)
{
cin >> a[i];
}
}
void solve()
{
for (int i = 1; i <= n; ++ i)
{
int x = get(i), y = min(a[i * 2], a[i * 2 + 1]);
if (x < min(a[i * 2], a[i * 2 + 1]))
{
cout << x << ' ';
recolor(i, x);
}
else
{
cout << y << ' ';
if (a[i * 2] < a[i * 2 + 1])
{
dp[i * 2] = 1;
dp[i * 2 + 1] = 0;
}
else
{
dp[i * 2] = 2;
dp[i * 2 + 1] = 1;
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen(TASK".INP", "r"))
{
freopen(TASK".INP", "r", stdin);
//freopen(TASK".OUT", "w", stdout);
}
int t = 1;
bool typetest = false;
if (typetest)
{
cin >> t;
}
for (int __ = 1; __ <= t; ++ __)
{
//cout << "Case #" << __ << ":" << '\n';
read();
solve();
}
}
Compilation message
swap.cpp: In function 'int get(int)':
swap.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type]
41 | }
| ^
swap.cpp: In function 'int main()':
swap.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
124 | freopen(TASK".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
