oj.uz

Submission #668526

# Submission time Handle Problem Language Result Execution time Memory
668526 2022-12-04T03:25:28 Z BlackJack Swap (BOI16_swap) C++11
100 / 100
 900 ms 232688 KB 
#include<bits/stdc++.h>
using namespace std;

void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"
#define fi first
#define se second

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
using db = long double;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;

void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    if(sz(NAME)) {
        freopen((NAME + ".inp").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}

tcT> bool ckmin(T&a, const T&b) {
    return b < a ? a=b,1 : 0; }
tcT> bool ckmax(T&a, const T&b) {
    return b > a ? a=b,1 : 0; }

const int MOD = 1e9 + 7;
const ll INF = 1e18;

const int LG = 18;

const int MX = 2e5+5;

int N;

int A[MX];

vi dp[MX][LG<<1];

bool need[MX][LG<<1];

void mrg(vi& res, const vi&a, const vi&b) {
    for(int i = 0, j = 0, step = 1; i < sz(a) || j < sz(b); i += step, j += step, step <<= 1) {
        for(int k = 0; k < step && i + k < sz(a); k++)
            res.pb(a[i+k]);
        for(int k = 0; k < step && j + k < sz(b); k++)
            res.pb(b[j+k]);
    }
}

void solve() {
    cin >> N;
    FOR(i,1,N+1) cin >> A[i];
    need[1][0] = 1;
    for(int i = 1; 2*i + 1 <= N; i++) {
        F0R(j, LG<<1) if(need[i][j]) {
            int b = (i >> (j>>1)) ^ (j&1);
            if(A[i<<1|1] < A[i<<1] && A[i<<1|1] < A[b]) {
                need[i<<1][0] = need[i<<1|1][1] = true;
                if(j + 2 < (LG<<1)) need[i<<1|1][j+2] = need[i<<1][j+2] = true;
            }
            else {
                need[i<<1][0] = need[i<<1|1][0] = 1;
                if(j + 2 < (LG<<1)) need[i<<1][j+2] = 1;
            }
        }
    }

    ROF(i,1,N+1) {
        F0R(j, LG<<1) if(need[i][j]) {
            int b = (i >> (j>>1)) ^ (j&1);
            if((i<<1|1) <= N) {
                if(A[i<<1|1] < A[i<<1] && A[i<<1|1] < A[b]) {
                    vi opt1 = {A[i<<1|1]}, opt2 = opt1;
                    mrg(opt1, dp[i<<1][0], dp[i<<1|1][j+2]);
                    mrg(opt2, dp[i<<1][j+2], dp[i<<1|1][1]);
                    dp[i][j] = min(opt1, opt2);
                }
                else {
                    if(A[i<<1] < A[b] && A[i<<1] < A[i<<1|1]) {
                        dp[i][j] = {A[i<<1]};
                        mrg(dp[i][j], dp[i<<1][j+2], dp[i<<1|1][0]);
                    }
                    else {
                        dp[i][j] = {A[b]};
                        mrg(dp[i][j], dp[i<<1][0], dp[i<<1|1][0]);
                    }
                }
            }
            else {
                if((i<<1) <= N) {
                    dp[i][j] = {min(A[b], A[i<<1]), max(A[b], A[i<<1])};
                }
                else {
                    dp[i][j] = {A[b]};
                }
            }
        }
        if((i<<1|1) <= N) {
            F0R(j, LG<<1) {
                if(need[i<<1][j]) vi().swap(dp[i<<1][j]);
                if(need[i<<1|1][j]) vi().swap(dp[i<<1|1][j]);
            }
        }
    }
    each(e, dp[1][0]) cout << e << " ";
    cout << nl;
}

int main() {
    setIO();

    int t=1;
    //cin>>t;
    while(t-->0) {
        solve();
    }

    return 0;
}

Compilation message

swap.cpp: In function 'void setIO(std::string)':
swap.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen((NAME + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
swap.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 169384 KB Output is correct
2 Correct 79 ms 169284 KB Output is correct
3 Correct 74 ms 169376 KB Output is correct
4 Correct 75 ms 169364 KB Output is correct
5 Correct 81 ms 169396 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 169384 KB Output is correct
2 Correct 79 ms 169284 KB Output is correct
3 Correct 74 ms 169376 KB Output is correct
4 Correct 75 ms 169364 KB Output is correct
5 Correct 81 ms 169396 KB Output is correct
6 Correct 74 ms 169312 KB Output is correct
7 Correct 76 ms 169276 KB Output is correct
8 Correct 87 ms 169300 KB Output is correct
9 Correct 77 ms 169316 KB Output is correct
10 Correct 83 ms 169392 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 169384 KB Output is correct
2 Correct 79 ms 169284 KB Output is correct
3 Correct 74 ms 169376 KB Output is correct
4 Correct 75 ms 169364 KB Output is correct
5 Correct 81 ms 169396 KB Output is correct
6 Correct 74 ms 169312 KB Output is correct
7 Correct 76 ms 169276 KB Output is correct
8 Correct 87 ms 169300 KB Output is correct
9 Correct 77 ms 169316 KB Output is correct
10 Correct 83 ms 169392 KB Output is correct
11 Correct 77 ms 169420 KB Output is correct
12 Correct 79 ms 169484 KB Output is correct
13 Correct 84 ms 169452 KB Output is correct
14 Correct 80 ms 169592 KB Output is correct
15 Correct 78 ms 169560 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 169384 KB Output is correct
2 Correct 79 ms 169284 KB Output is correct
3 Correct 74 ms 169376 KB Output is correct
4 Correct 75 ms 169364 KB Output is correct
5 Correct 81 ms 169396 KB Output is correct
6 Correct 74 ms 169312 KB Output is correct
7 Correct 76 ms 169276 KB Output is correct
8 Correct 87 ms 169300 KB Output is correct
9 Correct 77 ms 169316 KB Output is correct
10 Correct 83 ms 169392 KB Output is correct
11 Correct 77 ms 169420 KB Output is correct
12 Correct 79 ms 169484 KB Output is correct
13 Correct 84 ms 169452 KB Output is correct
14 Correct 80 ms 169592 KB Output is correct
15 Correct 78 ms 169560 KB Output is correct
16 Correct 130 ms 174344 KB Output is correct
17 Correct 135 ms 174396 KB Output is correct
18 Correct 135 ms 174532 KB Output is correct
19 Correct 254 ms 183612 KB Output is correct
20 Correct 253 ms 183448 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 169384 KB Output is correct
2 Correct 79 ms 169284 KB Output is correct
3 Correct 74 ms 169376 KB Output is correct
4 Correct 75 ms 169364 KB Output is correct
5 Correct 81 ms 169396 KB Output is correct
6 Correct 74 ms 169312 KB Output is correct
7 Correct 76 ms 169276 KB Output is correct
8 Correct 87 ms 169300 KB Output is correct
9 Correct 77 ms 169316 KB Output is correct
10 Correct 83 ms 169392 KB Output is correct
11 Correct 77 ms 169420 KB Output is correct
12 Correct 79 ms 169484 KB Output is correct
13 Correct 84 ms 169452 KB Output is correct
14 Correct 80 ms 169592 KB Output is correct
15 Correct 78 ms 169560 KB Output is correct
16 Correct 130 ms 174344 KB Output is correct
17 Correct 135 ms 174396 KB Output is correct
18 Correct 135 ms 174532 KB Output is correct
19 Correct 254 ms 183612 KB Output is correct
20 Correct 253 ms 183448 KB Output is correct
21 Correct 317 ms 189516 KB Output is correct
22 Correct 331 ms 189748 KB Output is correct
23 Correct 324 ms 189704 KB Output is correct
24 Correct 897 ms 232552 KB Output is correct
25 Correct 900 ms 232688 KB Output is correct