oj.uz

Submission #328639

# Submission time Handle Problem Language Result Execution time Memory
328639 2020-11-17T11:42:45 Z doowey Swap (BOI16_swap) C++14
68 / 100
 492 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 1;
const int LOG = 18;
vector<int> dp[2*N*LOG];
int idx = 0;

int n;
int a[N];

map<int, int> ids[N]; // looks bad but first subtasks should work

void unite(vector<int> &c, vector<int> &a, vector<int> &b){
    int q = 1;
    int f0 = 0, f1 = 0;
    int dq = c.size() + a.size() + b.size();
    int sh = c.size();
    c.resize(dq);
    while(f0 < a.size() || f1 < b.size()){
        for(int j = 0; j < q; j ++ ){
            if(f0 < a.size()){
                c[sh]=a[f0];
                sh++;
                f0 ++ ;
            }
        }
        for(int j = 0 ; j < q; j ++ ){
            if(f1 < b.size()){
                c[sh]=b[f1];
                sh++;
                f1 ++ ;
            }
        }
        q <<= 1;
    }
}

const int INF = (int)1e9;

void solve(int id, int x){
    if(x == INF) return;
    if(ids[id].count(x)) return;
    idx ++ ;
    ids[id][x] = idx;
    int cid = idx;
    if(id * 2 > n){
        dp[cid]={x};
        return;
    }
    if(id * 2 + 1 > n){
        if(x < a[id * 2]){
            dp[cid]={x,a[id*2]};
        }
        else{
            dp[cid]={a[id*2],x};
        }
        return;
    }
    int fa = a[id*2];
    int fb = a[id*2+1];
    if(x < fa && x < fb){
        solve(id*2, fa);
        solve(id*2+1, fb);
        vector<int> sol = {x};
        unite(sol,dp[ids[id*2][fa]],dp[ids[id*2+1][fb]]);
        dp[cid]=sol;
        return;
    }
    if(fa < x && fa < fb){
        solve(id*2, x);
        solve(id*2+1, fb);
        vector<int>sol = {fa};
        unite(sol, dp[ids[id*2][x]], dp[ids[id*2+1][fb]]);
        dp[cid]=sol;
        return;
    }
    solve(id*2, x);
    solve(id*2+1, fa);
    solve(id*2, fa);
    solve(id*2+1, x);
    // 2n log n states max
    vector<int> aa = {fb}, bb = {fb};
    unite(aa, dp[ids[id*2][x]], dp[ids[id*2+1][fa]]);
    unite(bb, dp[ids[id*2][fa]], dp[ids[id*2+1][x]]);
    dp[cid]=min(aa, bb);
}

int main(){
    fastIO;
    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> a[i];
    }
    solve(1, a[1]);
    for(auto x : dp[ids[1][a[1]]])
        cout << x << " ";
    cout << "\n";
    return 0;
}

Compilation message

swap.cpp: In function 'void unite(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
swap.cpp:29:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     while(f0 < a.size() || f1 < b.size()){
      |           ~~~^~~~~~~~~~
swap.cpp:29:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     while(f0 < a.size() || f1 < b.size()){
      |                            ~~~^~~~~~~~~~
swap.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             if(f0 < a.size()){
      |                ~~~^~~~~~~~~~
swap.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             if(f1 < b.size()){
      |                ~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 178924 KB Output is correct
2 Correct 116 ms 178796 KB Output is correct
3 Correct 111 ms 178796 KB Output is correct
4 Correct 107 ms 178796 KB Output is correct
5 Correct 108 ms 178796 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 178924 KB Output is correct
2 Correct 116 ms 178796 KB Output is correct
3 Correct 111 ms 178796 KB Output is correct
4 Correct 107 ms 178796 KB Output is correct
5 Correct 108 ms 178796 KB Output is correct
6 Correct 110 ms 178796 KB Output is correct
7 Correct 109 ms 178796 KB Output is correct
8 Correct 107 ms 178796 KB Output is correct
9 Correct 109 ms 178796 KB Output is correct
10 Correct 108 ms 178796 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 178924 KB Output is correct
2 Correct 116 ms 178796 KB Output is correct
3 Correct 111 ms 178796 KB Output is correct
4 Correct 107 ms 178796 KB Output is correct
5 Correct 108 ms 178796 KB Output is correct
6 Correct 110 ms 178796 KB Output is correct
7 Correct 109 ms 178796 KB Output is correct
8 Correct 107 ms 178796 KB Output is correct
9 Correct 109 ms 178796 KB Output is correct
10 Correct 108 ms 178796 KB Output is correct
11 Correct 111 ms 179072 KB Output is correct
12 Correct 108 ms 179180 KB Output is correct
13 Correct 109 ms 179052 KB Output is correct
14 Correct 121 ms 179692 KB Output is correct
15 Correct 115 ms 179564 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 178924 KB Output is correct
2 Correct 116 ms 178796 KB Output is correct
3 Correct 111 ms 178796 KB Output is correct
4 Correct 107 ms 178796 KB Output is correct
5 Correct 108 ms 178796 KB Output is correct
6 Correct 110 ms 178796 KB Output is correct
7 Correct 109 ms 178796 KB Output is correct
8 Correct 107 ms 178796 KB Output is correct
9 Correct 109 ms 178796 KB Output is correct
10 Correct 108 ms 178796 KB Output is correct
11 Correct 111 ms 179072 KB Output is correct
12 Correct 108 ms 179180 KB Output is correct
13 Correct 109 ms 179052 KB Output is correct
14 Correct 121 ms 179692 KB Output is correct
15 Correct 115 ms 179564 KB Output is correct
16 Correct 176 ms 193668 KB Output is correct
17 Correct 174 ms 193320 KB Output is correct
18 Correct 174 ms 193696 KB Output is correct
19 Correct 492 ms 252908 KB Output is correct
20 Correct 492 ms 251988 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 178924 KB Output is correct
2 Correct 116 ms 178796 KB Output is correct
3 Correct 111 ms 178796 KB Output is correct
4 Correct 107 ms 178796 KB Output is correct
5 Correct 108 ms 178796 KB Output is correct
6 Correct 110 ms 178796 KB Output is correct
7 Correct 109 ms 178796 KB Output is correct
8 Correct 107 ms 178796 KB Output is correct
9 Correct 109 ms 178796 KB Output is correct
10 Correct 108 ms 178796 KB Output is correct
11 Correct 111 ms 179072 KB Output is correct
12 Correct 108 ms 179180 KB Output is correct
13 Correct 109 ms 179052 KB Output is correct
14 Correct 121 ms 179692 KB Output is correct
15 Correct 115 ms 179564 KB Output is correct
16 Correct 176 ms 193668 KB Output is correct
17 Correct 174 ms 193320 KB Output is correct
18 Correct 174 ms 193696 KB Output is correct
19 Correct 492 ms 252908 KB Output is correct
20 Correct 492 ms 251988 KB Output is correct
21 Correct 397 ms 241856 KB Output is correct
22 Correct 391 ms 242640 KB Output is correct
23 Correct 397 ms 242912 KB Output is correct
24 Runtime error 393 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -