oj.uz

Submission #573440

# Submission time Handle Problem Language Result Execution time Memory
573440 2022-06-06T15:47:48 Z Tien_Noob Swap (BOI16_swap) C++17
100 / 100
 53 ms 5200 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 get(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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1864 KB Output is correct
2 Correct 1 ms 1860 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 2 ms 1876 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1864 KB Output is correct
2 Correct 1 ms 1860 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 2 ms 1876 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 2 ms 1876 KB Output is correct
8 Correct 1 ms 1876 KB Output is correct
9 Correct 2 ms 1876 KB Output is correct
10 Correct 2 ms 1876 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1864 KB Output is correct
2 Correct 1 ms 1860 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 2 ms 1876 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 2 ms 1876 KB Output is correct
8 Correct 1 ms 1876 KB Output is correct
9 Correct 2 ms 1876 KB Output is correct
10 Correct 2 ms 1876 KB Output is correct
11 Correct 1 ms 1876 KB Output is correct
12 Correct 1 ms 1876 KB Output is correct
13 Correct 1 ms 1868 KB Output is correct
14 Correct 1 ms 1876 KB Output is correct
15 Correct 1 ms 1876 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1864 KB Output is correct
2 Correct 1 ms 1860 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 2 ms 1876 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 2 ms 1876 KB Output is correct
8 Correct 1 ms 1876 KB Output is correct
9 Correct 2 ms 1876 KB Output is correct
10 Correct 2 ms 1876 KB Output is correct
11 Correct 1 ms 1876 KB Output is correct
12 Correct 1 ms 1876 KB Output is correct
13 Correct 1 ms 1868 KB Output is correct
14 Correct 1 ms 1876 KB Output is correct
15 Correct 1 ms 1876 KB Output is correct
16 Correct 10 ms 2644 KB Output is correct
17 Correct 10 ms 2644 KB Output is correct
18 Correct 12 ms 2560 KB Output is correct
19 Correct 16 ms 2560 KB Output is correct
20 Correct 13 ms 2648 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1864 KB Output is correct
2 Correct 1 ms 1860 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 2 ms 1876 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 2 ms 1876 KB Output is correct
8 Correct 1 ms 1876 KB Output is correct
9 Correct 2 ms 1876 KB Output is correct
10 Correct 2 ms 1876 KB Output is correct
11 Correct 1 ms 1876 KB Output is correct
12 Correct 1 ms 1876 KB Output is correct
13 Correct 1 ms 1868 KB Output is correct
14 Correct 1 ms 1876 KB Output is correct
15 Correct 1 ms 1876 KB Output is correct
16 Correct 10 ms 2644 KB Output is correct
17 Correct 10 ms 2644 KB Output is correct
18 Correct 12 ms 2560 KB Output is correct
19 Correct 16 ms 2560 KB Output is correct
20 Correct 13 ms 2648 KB Output is correct
21 Correct 41 ms 5196 KB Output is correct
22 Correct 40 ms 5196 KB Output is correct
23 Correct 40 ms 5100 KB Output is correct
24 Correct 51 ms 5120 KB Output is correct
25 Correct 53 ms 5200 KB Output is correct