Submission #873398

#	Time	Username	Problem	Language	Result	Execution time	Memory
873398		anha3k25cvp	Swap (BOI16_swap)	C++14	100 / 100	606 ms	227664 KiB

swap

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>

using namespace std;

const int N = 5 + 1e5;
const int inf = 7 + 1e9;

vector <int> a, v1, v2;
vector <vector <bool>> f;
vector <vector <vector <int>>> g;

void Merge(vector <int> &a, vector <int> &b, vector <int> &c) {
    for (int i = 0, j = 0, l = 1; i < b.size() || j < c.size(); i += l, j += l, l *= 2) {
        for (int pos = 0; pos < l && i + pos < b.size(); pos ++)
            a.push_back(b[i + pos]);
        for (int pos = 0; pos < l && j + pos < c.size(); pos ++)
            a.push_back(c[j + pos]);
    }
}

int main() {
#define TASKNAME ""
    ios_base :: sync_with_stdio (0);
    cin.tie (0);
    if ( fopen( TASKNAME".inp", "r" ) ) {
        freopen (TASKNAME".inp", "r", stdin);
        freopen (TASKNAME".out", "w", stdout);
    }
    int n;
    cin >> n;
    a.assign(n + 1, 0);
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    int logn;
    for (logn = 1; (1 << logn) <= n; logn ++);
    logn *= 2;
    f.assign(logn, vector <bool> (n + 1, 0));
    f[0][1] = 1;
    for (int i = 1; i * 2 + 1 <= n; i ++)
        for (int j = 0; j < logn; j ++)
            if (f[j][i]) {
                int pos = i >> j / 2 ^ j & 1;
                if (a[2 * i + 1] < a[pos] && a[2 * i + 1] < a[2 * i])
                    f[j + 2][2 * i] = f[0][2 * i] = f[j + 2][2 * i + 1] = f[1][2 * i + 1] = 1;
                else if (a[2 * i] < a[pos])
                    f[j + 2][2 * i] = f[0][2 * i + 1] = 1;
                else
                    f[0][2 * i] = f[0][2 * i + 1] = 1;
            }
    g.assign(logn, vector <vector <int>> (n + 1));
    for (int i = n; i > 0; i --) {
        for (int j = 0; j < logn; j ++)
            if (f[j][i]) {
                int pos = i >> j / 2 ^ j & 1;
                if (2 * i + 1 <= n) {
                    if (a[2 * i + 1] < a[pos] && a[2 * i + 1] < a[2 * i]) {
                        v1 = {a[2 * i + 1]};
                        v2 = {a[2 * i + 1]};
                        Merge(v1, g[j + 2][2 * i], g[1][2 * i + 1]);
                        Merge(v2, g[0][2 * i], g[j + 2][2 * i + 1]);
                        g[j][i] = min(v1, v2);
                    }
                    else if (a[2 * i] < a[pos]) {
                        g[j][i].push_back(a[2 * i]);
                        Merge(g[j][i], g[j + 2][2 * i], g[0][2 * i + 1]);
                    }
                    else {
                        g[j][i].push_back(a[pos]);
                        Merge(g[j][i], g[0][2 * i], g[0][2 * i + 1]);
                    }
                }
                else if (i * 2 <= n)
                    g[j][i] = {min(a[pos], a[2 * i]), max(a[pos], a[2 * i])};
                else
                    g[j][i] = {a[pos]};
            }
        if (2 * i + 1 <= n)
            for (int val = 0; val < 2; val ++)
                for (int j = 0; j < logn; j ++)
                    if (f[j][2 * i + val])
                        vector <int> ().swap(g[j][2 * i + val]);
    }
    for (int u : g[0][1])
        cout << u << ' ';
    return 0;
}

Compilation message (stderr)

swap.cpp: In function 'void Merge(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
swap.cpp:19:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 0, j = 0, l = 1; i < b.size() || j < c.size(); i += l, j += l, l *= 2) {
      |                                   ~~^~~~~~~~~~
swap.cpp:19:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 0, j = 0, l = 1; i < b.size() || j < c.size(); i += l, j += l, l *= 2) {
      |                                                   ~~^~~~~~~~~~
swap.cpp:20:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for (int pos = 0; pos < l && i + pos < b.size(); pos ++)
      |                                      ~~~~~~~~^~~~~~~~~~
swap.cpp:22:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for (int pos = 0; pos < l && j + pos < c.size(); pos ++)
      |                                      ~~~~~~~~^~~~~~~~~~
swap.cpp: In function 'int main()':
swap.cpp:48:42: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   48 |                 int pos = i >> j / 2 ^ j & 1;
      |                                        ~~^~~
swap.cpp:60:42: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   60 |                 int pos = i >> j / 2 ^ j & 1;
      |                                        ~~^~~
swap.cpp:32:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         freopen (TASKNAME".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
swap.cpp:33:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen (TASKNAME".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 27 / 27
• Subtask 4: 20 / 20
• Subtask 5: 32 / 32