oj.uz

답안 #563368

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
563368 2022-05-17T03:04:48 Z generic_placeholder_name Swap (BOI16_swap) C++17
48 / 100
 1000 ms 16064 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma,popcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define gcd __gcd
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rep(i, n) for (int i=0; i<(n); i++)
#define rep1(i, n) for (int i=1; i<=(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl "\n"

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
template<typename T, typename cmp = less<T>>
using ordered_set = tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;

constexpr int N = 2e5 + 5;

int n;
int a[N];
vector<int> idx[N];
vector<int> rsv[N];

vector<int> merge(const vector<int>& a, const vector<int>& b, int i) {
    auto& l = idx[i * 2], r = idx[i * 2 + 1];
    vector<int> ans;
    int p = 0, q = 0;
    while(p < l.size() || q < r.size()) {
        if(p == l.size() || (q != r.size() && r[q] < l[p])) ans.pb(b[q++]);
        else ans.pb(a[p++]);
    }
    return ans;
}

int cnt = 0;
vector<int> solve(int i) {
    cnt++;
    if(i > n) return {};
    if(i * 2 > n) return vi{a[i]};
    if(i * 2 == n) {
        return vi{min(a[i], a[i * 2]), max(a[i], a[i * 2])};
    }
    if(i * 4 > n) {
        int x = a[i], y = a[i * 2], z = a[i * 2 + 1];
        if(x < y && x < z) return vi{x, y, z};
        else if(y < x && y < z) return vi{y, x, z};
        else return vi{z, min(x, y), max(x, y)};
    }
    if(a[i] < a[i * 2] && a[i] < a[i * 2 + 1]) {
        vector<int> ans = merge(solve(i * 2), solve(i * 2 + 1), i);
        ans.insert(ans.begin(), a[i]);
        return ans;
    }
    else if(a[i * 2] < a[i] && a[i * 2] < a[i * 2 + 1]) {
        swap(a[i], a[i * 2]);
        vector<int> ans = merge(solve(i * 2), solve(i * 2 + 1), i);
        ans.insert(ans.begin(), a[i]);
        return ans;
    }
    else {
        swap(a[i], a[i * 2 + 1]);
        rsv[i].clear();
        for(int j: idx[i]) rsv[i].pb(a[j]);
        vector<int> ans = merge(solve(i * 2), solve(i * 2 + 1), i);
        for(int j = 0; j < idx[i].size(); j++) {
            a[idx[i][j]] = rsv[i][j];
        }
        swap(a[i * 2], a[i * 2 + 1]);
        vector<int> ans2 = merge(solve(i * 2), solve(i * 2 + 1), i);
        if(ans2 < ans) ans.swap(ans2);
        else {
            for(int j = 0; j < idx[i].size(); j++) {
                a[idx[i][j]] = rsv[i][j];
            }
        }
        ans.insert(ans.begin(), a[i]);
        return ans;
    }
}

int32_t main() {
    fastio;
    cin >> n;
    for(int i = n; i >= 1; i--) {
        idx[i].pb(i);
        if(2 * i < n) {
            int p = 0, q = 0;
            auto &a = idx[2 * i], &b = idx[2 * i + 1];
            while(p < a.size() || q < b.size()) {
                if(p == a.size() || (q != b.size() && b[q] < a[p])) idx[i].pb(b[q++]);
                else idx[i].pb(a[p++]);
            }
        }
        else if(2 * i == n) {
            idx[i].insert(idx[i].end(), all(idx[2 * i]));
        }
    }
    //for(int i = 1; i <= n; i++) a[i] = i;
    //random_shuffle(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i++) cin >> a[i];
    auto ans = solve(1);
    //cout << cnt << endl;
    for(int x: ans) cout << x << ' '; cout << endl;
}

Compilation message

swap.cpp: In function 'std::vector<int> merge(const std::vector<int>&, const std::vector<int>&, int)':
swap.cpp:56:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     while(p < l.size() || q < r.size()) {
      |           ~~^~~~~~~~~~
swap.cpp:56:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     while(p < l.size() || q < r.size()) {
      |                           ~~^~~~~~~~~~
swap.cpp:57:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         if(p == l.size() || (q != r.size() && r[q] < l[p])) ans.pb(b[q++]);
      |            ~~^~~~~~~~~~~
swap.cpp:57:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         if(p == l.size() || (q != r.size() && r[q] < l[p])) ans.pb(b[q++]);
      |                              ~~^~~~~~~~~~~
swap.cpp: In function 'std::vector<int> solve(int)':
swap.cpp:93:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         for(int j = 0; j < idx[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~
swap.cpp:100:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             for(int j = 0; j < idx[i].size(); j++) {
      |                            ~~^~~~~~~~~~~~~~~
swap.cpp: In function 'int32_t main()':
swap.cpp:117:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |             while(p < a.size() || q < b.size()) {
      |                   ~~^~~~~~~~~~
swap.cpp:117:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |             while(p < a.size() || q < b.size()) {
      |                                   ~~^~~~~~~~~~
swap.cpp:118:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |                 if(p == a.size() || (q != b.size() && b[q] < a[p])) idx[i].pb(b[q++]);
      |                    ~~^~~~~~~~~~~
swap.cpp:118:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |                 if(p == a.size() || (q != b.size() && b[q] < a[p])) idx[i].pb(b[q++]);
      |                                      ~~^~~~~~~~~~~
swap.cpp:131:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  131 |     for(int x: ans) cout << x << ' '; cout << endl;
      |     ^~~
swap.cpp:131:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  131 |     for(int x: ans) cout << x << ' '; cout << endl;
      |                                       ^~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 6 ms 9600 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 6 ms 9600 KB Output is correct
6 Correct 6 ms 9708 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 6 ms 9600 KB Output is correct
6 Correct 6 ms 9708 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 7 ms 9812 KB Output is correct
12 Correct 9 ms 9812 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 19 ms 9768 KB Output is correct
15 Correct 16 ms 9836 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 6 ms 9600 KB Output is correct
6 Correct 6 ms 9708 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 7 ms 9812 KB Output is correct
12 Correct 9 ms 9812 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 19 ms 9768 KB Output is correct
15 Correct 16 ms 9836 KB Output is correct
16 Correct 216 ms 15888 KB Output is correct
17 Correct 167 ms 15792 KB Output is correct
18 Correct 226 ms 16064 KB Output is correct
19 Execution timed out 1081 ms 15364 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 6 ms 9600 KB Output is correct
6 Correct 6 ms 9708 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 7 ms 9812 KB Output is correct
12 Correct 9 ms 9812 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 19 ms 9768 KB Output is correct
15 Correct 16 ms 9836 KB Output is correct
16 Correct 216 ms 15888 KB Output is correct
17 Correct 167 ms 15792 KB Output is correct
18 Correct 226 ms 16064 KB Output is correct
19 Execution timed out 1081 ms 15364 KB Time limit exceeded
20 Halted 0 ms 0 KB -