답안 #59782 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59782	2018-07-23T06:02:09 Z	Benq	Swap (BOI16_swap)	C++11	100 / 100	313 ms	22948 KB

swap

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

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 200001;

map<pi,int> bes;
int n, p[MX];

int get(int ind, int y) {
    if (bes.count({ind,y})) return bes[{ind,y}];
    if (2*ind > n) return ind;
    if (2*ind+1 > n) {
        if (y > p[2*ind]) return 2*ind;
        return ind;
    }
    
    if (y < min(p[2*ind],p[2*ind+1])) return bes[{ind,y}] = ind;
    if (p[2*ind] < min(y,p[2*ind+1])) return bes[{ind,y}] = get(2*ind,y);
    
    int mn = min(y,p[2*ind]);
    if (get(2*ind,mn) < get(2*ind+1,mn)) {
        if (mn == y) return bes[{ind,y}] = get(2*ind,y);
        return bes[{ind,y}] = get(2*ind+1,y);
    } else {
        if (mn == y) return bes[{ind,y}] = get(2*ind+1,y);
        return bes[{ind,y}] = get(2*ind,y);
    }
}

void solve(int ind) {
    if (2*ind > n) return;
    if (2*ind+1 > n) {
        if (p[ind] > p[2*ind]) swap(p[ind],p[2*ind]);
        return;
    }
    
    if (p[ind] < min(p[2*ind],p[2*ind+1])) {
        
    } else if (p[2*ind] < min(p[ind],p[2*ind+1])) {
        swap(p[2*ind],p[ind]);
    } else {
        int mn = min(p[ind],p[2*ind]), mx = max(p[ind],p[2*ind]);
        
        p[ind] = p[2*ind+1];
        if (get(2*ind,mn) < get(2*ind+1,mn)) {
            p[2*ind] = mn, p[2*ind+1] = mx;
        } else {
            p[2*ind] = mx, p[2*ind+1] = mn;    
        }
    }
    solve(ind+1);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    FOR(i,1,n+1) cin >> p[i];
    solve(1);
    FOR(i,1,n+1) cout << p[i] << " ";
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	3 ms	564 KB	Output is correct
4	Correct	3 ms	564 KB	Output is correct
5	Correct	3 ms	564 KB	Output is correct

Subtask #2
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	3 ms	564 KB	Output is correct
4	Correct	3 ms	564 KB	Output is correct
5	Correct	3 ms	564 KB	Output is correct
6	Correct	3 ms	584 KB	Output is correct
7	Correct	3 ms	636 KB	Output is correct
8	Correct	3 ms	640 KB	Output is correct
9	Correct	4 ms	648 KB	Output is correct
10	Correct	3 ms	648 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	3 ms	564 KB	Output is correct
4	Correct	3 ms	564 KB	Output is correct
5	Correct	3 ms	564 KB	Output is correct
6	Correct	3 ms	584 KB	Output is correct
7	Correct	3 ms	636 KB	Output is correct
8	Correct	3 ms	640 KB	Output is correct
9	Correct	4 ms	648 KB	Output is correct
10	Correct	3 ms	648 KB	Output is correct
11	Correct	3 ms	656 KB	Output is correct
12	Correct	3 ms	660 KB	Output is correct
13	Correct	3 ms	664 KB	Output is correct
14	Correct	4 ms	668 KB	Output is correct
15	Correct	4 ms	672 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	3 ms	564 KB	Output is correct
4	Correct	3 ms	564 KB	Output is correct
5	Correct	3 ms	564 KB	Output is correct
6	Correct	3 ms	584 KB	Output is correct
7	Correct	3 ms	636 KB	Output is correct
8	Correct	3 ms	640 KB	Output is correct
9	Correct	4 ms	648 KB	Output is correct
10	Correct	3 ms	648 KB	Output is correct
11	Correct	3 ms	656 KB	Output is correct
12	Correct	3 ms	660 KB	Output is correct
13	Correct	3 ms	664 KB	Output is correct
14	Correct	4 ms	668 KB	Output is correct
15	Correct	4 ms	672 KB	Output is correct
16	Correct	31 ms	2596 KB	Output is correct
17	Correct	26 ms	2896 KB	Output is correct
18	Correct	40 ms	3196 KB	Output is correct
19	Correct	60 ms	5400 KB	Output is correct
20	Correct	72 ms	5684 KB	Output is correct

Subtask #5
32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	3 ms	564 KB	Output is correct
4	Correct	3 ms	564 KB	Output is correct
5	Correct	3 ms	564 KB	Output is correct
6	Correct	3 ms	584 KB	Output is correct
7	Correct	3 ms	636 KB	Output is correct
8	Correct	3 ms	640 KB	Output is correct
9	Correct	4 ms	648 KB	Output is correct
10	Correct	3 ms	648 KB	Output is correct
11	Correct	3 ms	656 KB	Output is correct
12	Correct	3 ms	660 KB	Output is correct
13	Correct	3 ms	664 KB	Output is correct
14	Correct	4 ms	668 KB	Output is correct
15	Correct	4 ms	672 KB	Output is correct
16	Correct	31 ms	2596 KB	Output is correct
17	Correct	26 ms	2896 KB	Output is correct
18	Correct	40 ms	3196 KB	Output is correct
19	Correct	60 ms	5400 KB	Output is correct
20	Correct	72 ms	5684 KB	Output is correct
21	Correct	100 ms	10000 KB	Output is correct
22	Correct	94 ms	11332 KB	Output is correct
23	Correct	117 ms	12772 KB	Output is correct
24	Correct	265 ms	21688 KB	Output is correct
25	Correct	313 ms	22948 KB	Output is correct

답안 #59782

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 11.0 / 11.0

Subtask #3 27.0 / 27.0

Subtask #4 20.0 / 20.0

Subtask #5 32.0 / 32.0

Subtask #1
10.0 / 10.0

Subtask #2
11.0 / 11.0

Subtask #3
27.0 / 27.0

Subtask #4
20.0 / 20.0

Subtask #5
32.0 / 32.0