oj.uz

Submission #1107572

# Submission time Handle Problem Language Result Execution time Memory
1107572 2024-11-01T14:20:29 Z koukirocks Swap (BOI16_swap) C++17
100 / 100
 183 ms 29256 KB 
#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=2e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<typename T>
using vvector = vector<vector<T>>;
 
map<pii,int> rec;
int search(int v,int val,vector<int> &a,int n) {
    if (rec.find({v,val})!=rec.end()) return rec[{v,val}];
    if ((v<<1)<=n) {
        if ((v<<1|1)<=n) {
            int mn = min({val,a[v<<1],a[v<<1|1]});
            if (mn==val) return rec[{v,val}]=v;
            else if (mn==a[v<<1]) return rec[{v,val}]=search(v<<1,val,a,n);
            else {
                int lc=a[v<<1],rc=val;
                if (rc<lc) return rec[{v,val}]=min(search(v<<1,rc,a,n),search(v<<1|1,rc,a,n));
                else {
                    int lp1=search(v<<1,lc,a,n),lp2=search(v<<1|1,lc,a,n);
                    if (lp1<lp2) return rec[{v,val}]=search(v<<1|1,val,a,n);
                    else return rec[{v,val}]=search(v<<1,val,a,n);
                }
            }
        } else {
            if (val<a[v<<1]) return rec[{v,val}]=v;
            return rec[{v,val}]=search(v<<1,val,a,n);
        }
    } else return rec[{v,val}]=v;
}
 
void dfs(int v,int val,vector<int> &ans,vector<int> &a,int n) {
    // cout<<v<<" "<<val<<" v val\n";
    if ((v<<1)<=n) {
        if ((v<<1|1)<=n) {
            int mn = min({val,a[v<<1],a[v<<1|1]});
            ans[v]=mn;
            if (mn==val) {
                dfs(v<<1,a[v<<1],ans,a,n);
                dfs(v<<1|1,a[v<<1|1],ans,a,n);
            } else if (mn==a[v<<1]) {
                dfs(v<<1,val,ans,a,n);
                dfs(v<<1|1,a[v<<1|1],ans,a,n);
            } else {
                int lc=a[v<<1],rc=val;
                if (lc>rc) swap(lc,rc);
                int lp1=search(v<<1,lc,a,n),lp2=search(v<<1|1,lc,a,n);
                if (lp1<lp2) {
                    dfs(v<<1,lc,ans,a,n);
                    dfs(v<<1|1,rc,ans,a,n);
                } else {
                    dfs(v<<1,rc,ans,a,n);
                    dfs(v<<1|1,lc,ans,a,n);
                }
            }
        } else {
            ans[v]=min(a[v<<1],val);
            dfs(v<<1,max(val,a[v<<1]),ans,a,n);
        }
    } else ans[v]=val;
}
 
int main() {
    speed;
    int n;
    cin>>n;
    vector<int> a(n+1);
    for (int i=1;i<=n;i++) {
        cin>>a[i];
    }
    vector<int> ans(n+1);
    dfs(1,a[1],ans,a,n);
    for (int i=1;i<=n;i++) {
        cout<<ans[i]<<" ";
    }
    return 0;
}
/*
20
13 8 2 19 7 15 5 12 9 17 3 16 4 18 10 1 11 6 14 20
*/
    //               13
    //          8         2
    //      19    7    15    5
    //     12 9 17 3 16 4 18 10
    //    1 11 6 14 20

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 592 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 592 KB Output is correct
16 Correct 18 ms 3744 KB Output is correct
17 Correct 16 ms 3664 KB Output is correct
18 Correct 19 ms 3664 KB Output is correct
19 Correct 36 ms 7508 KB Output is correct
20 Correct 37 ms 7396 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 592 KB Output is correct
16 Correct 18 ms 3744 KB Output is correct
17 Correct 16 ms 3664 KB Output is correct
18 Correct 19 ms 3664 KB Output is correct
19 Correct 36 ms 7508 KB Output is correct
20 Correct 37 ms 7396 KB Output is correct
21 Correct 70 ms 13772 KB Output is correct
22 Correct 73 ms 13896 KB Output is correct
23 Correct 70 ms 13768 KB Output is correct
24 Correct 171 ms 29256 KB Output is correct
25 Correct 183 ms 29256 KB Output is correct