Submission #320437

#	Time	Username	Problem	Language	Result	Execution time	Memory
320437		caoash	Swap (BOI16_swap)	C++17	48 / 100	1092 ms	11504 KiB

swap

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
 
#include <bits/stdc++.h> 
using namespace std;
 
using ll = long long;
 
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
 
using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair
 
const int MX = 200005;

namespace IO {
    const int BUFFER_SIZE = 1 << 15;
 
    char input_buffer[BUFFER_SIZE];
    int input_pos = 0, input_len = 0;
 
    char output_buffer[BUFFER_SIZE];
    int output_pos = 0;
 
    char number_buffer[100];
    uint8_t lookup[100];
 
    void _update_input_buffer() {
        input_len = fread(input_buffer, sizeof(char), BUFFER_SIZE, stdin);
        input_pos = 0;
 
        if (input_len == 0)
            input_buffer[0] = EOF;
    }
 
    inline char next_char(bool advance = true) {
        if (input_pos >= input_len)
            _update_input_buffer();
 
        return input_buffer[advance ? input_pos++ : input_pos];
    }
 
    template<typename T>
    inline void read_int(T &number) {
        bool negative = false;
        number = 0;
 
        while (!isdigit(next_char(false)))
            if (next_char() == '-')
                negative = true;
 
        do {
            number = 10 * number + (next_char() - '0');
        } while (isdigit(next_char(false)));
 
        if (negative)
            number = -number;
    }
 
    template<typename T, typename... Args>
    inline void read_int(T &number, Args &... args) {
        read_int(number);
        read_int(args...);
    }
 
    void _flush_output() {
        fwrite(output_buffer, sizeof(char), output_pos, stdout);
        output_pos = 0;
    }
 
    inline void write_char(char c) {
        if (output_pos == BUFFER_SIZE)
            _flush_output();
 
        output_buffer[output_pos++] = c;
    }
 
    template<typename T>
    inline void write_int(T number, char after = '\0') {
        if (number < 0) {
            write_char('-');
            number = -number;
        }
 
        int length = 0;
 
        while (number >= 10) {
            uint8_t lookup_value = lookup[number % 100];
            number /= 100;
            number_buffer[length++] = (lookup_value & 15) + '0';
            number_buffer[length++] = (lookup_value >> 4) + '0';
        }
 
        if (number != 0 || length == 0)
            write_char(number + '0');
 
        for (int i = length - 1; i >= 0; i--)
            write_char(number_buffer[i]);
 
        if (after)
            write_char(after);
    }
 
    void init() {
        // Make sure _flush_output() is called at the end of the program.
        bool exit_success = atexit(_flush_output) == 0;
        assert(exit_success);
 
        for (int i = 0; i < 100; i++)
            lookup[i] = (i / 10 << 4) + i % 10;
    }
}
 
struct hash_pair { 
    template <class T1, class T2> 
    size_t operator()(const pair<T1, T2>& p) const
    { 
        auto hash1 = hash<T1>{}(p.first); 
        auto hash2 = hash<T2>{}(p.second); 
        return hash1 ^ hash2; 
    } 
}; 
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
 
int n; int num[MX]; gp_hash_table<pi, vi, hash_pair> dp; 
 
void merge(vi &best, vi a, int x, vi b) {
    vi ret;
    ret.pb(x);
    int p1 = 0, p2 = 0;
    for (int i = 0; i < 36; i++) {
        if (p1 < sz(a)) {
            for (int j = 0; j < (1 << i); j++) {
                if (p1 < sz(a)) {
                    ret.pb(a[p1++]);
                }
                else {
                    break;
                }
            } 
        }
        if (p2 < sz(b)) {
            for (int j = 0; j < (1 << i); j++) {
                if (p2 < sz(b)) {
                    ret.pb(b[p2++]);
                } 
                else {
                    break;
                }
            }
        }
    }
    if (best.empty()) best = ret;
    else best = min(best, ret);
}
 
vi solve(int v, int c) {
    if (!dp[mp(v, c)].empty()) {
        return dp[mp(v, c)];
    }
    int l = 2 * v + 1, r = 2 * v + 2;
    if (l >= n) {
        return dp[mp(v, c)] = {c};
    }
    if (r >= n) {
        vi best; 
        vi fst = solve(l, num[l]);
        best.pb(c);
        for (int x : fst) best.pb(x);
        vi sec = solve(l, c);
        vi sbest;
        sbest.pb(num[l]);
        for (int x : sec) sbest.pb(x);
        return dp[mp(v, c)] = min(best, sbest);
    }
    vi best;
    // no swaps
    merge(best, solve(l, num[l]), c, solve(r, num[r]));
 
    // swap left
    if (l < n) {
        merge(best, solve(l, c), num[l], solve(r, num[r]));
    }
 
    // swap right
    if (r < n) {
        merge(best, solve(l, num[l]), num[r], solve(r, c));
    }
 
    // swap left, then right
    if (r < n) {
        merge(best, solve(l, c), num[r], solve(r, num[l]));
    }
    return dp[mp(v, c)] = best;
}
 
int main(){
    IO::init();
    IO::read_int(n);
    for (int i = 0; i < n; i++) {
        IO::read_int(num[i]);
    }
    solve(0, num[0]); 
    vi ans = dp[mp(0, num[0])];
    for (int i = 0; i < n; i++) {
        IO::write_int((int) ans[i], ' ');
    }
}

Compilation message (stderr)

swap.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
swap.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

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