oj.uz

Submission #834448

# Submission time Handle Problem Language Result Execution time Memory
834448 2023-08-22T14:28:40 Z Ronin13 Swap (BOI16_swap) C++17
48 / 100
 545 ms 262144 KB 
#include <bits/stdc++.h>
#define ll long long  
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int nmax = 200001;

vector <int> ans[nmax][37];
map <pii, int> mp;
int cur[nmax];
int a[nmax];

//vector <vector <int> > g(nmax);
vector <int> vv[nmax];
int n;

void bfs(int s){
    if(2 * s <= n && 2 * s + 1 <= n){
        queue <pii> q;
        q.push({2 * s, 0});
        q.push({2 * s + 1, 1});
        while(!q.empty()){
            int v = q.front().f;
            vv[s].pb(q.front().s);
            q.pop();
            if(2 * v <= n) q.push({2 * v, vv[s].back()});
            if(2 * v + 1 <= n) q.push({2 * v + 1, vv[s].back()});
        }

    }
}

vector <int> A, B;
vector <int> nx, ny;

int opt(int v, int x){
    if(mp[{v, x}] == 0) mp[{v, x}] = ++cur[v];
    else return mp[{v, x}];
    int c = mp[{v, x}];
    if(2 * v > n){
        ans[v][c] = {x};
        return c;
    }
    if(2 * v + 1 > n){
        if(a[2 * v] > x)
            ans[v][c]= {x, a[2 * v]};
        else ans[v][c] = {a[2 * v], x};
        return c;
    }
    vector <int> all = {x, a[2 * v], a[2 *v + 1]};
    sort(all.begin(), all.end());
    if(all[0] == x){
        int xx = opt(2 * v, a[2 * v]);
        int yy =  opt(2 * v+  1, a[ 2* v + 1]);
        A = ans[2 * v][xx];
        B = ans[2 * v + 1][yy];
        ans[v][c].pb(x);
        int inda, indb;
        inda = indb = 0;
        for(int to : vv[v]){
            if(!to) ans[v][c].pb(A[inda]), inda++;
            else ans[v][c].pb(B[indb]), indb++;
        }
        return c;
    }
    if(all[0] == a[2 * v]){
        int xx = opt(2 * v, x);
        int yy = opt(2 * v + 1, a[2 * v + 1]);
        A = ans[2 * v][xx];
        B = ans[2 * v + 1][yy];
        ans[v][c].pb(a[2 * v]);
        int inda, indb;
        inda = indb = 0;
        for(int to : vv[v]){
            if(!to) ans[v][c].pb(A[inda]), inda++;
            else ans[v][c].pb(B[indb]), indb++;
        }
        return c;
    }
    int x1 = opt(2 * v, all[1]), y1 = opt(2 * v+ 1, all[2]);
    int x2 = opt(2 * v, all[2]), y2 = opt(2 * v+ 1, all[1]);
  //  cout << x1 << ' ' << y1 << ' ' <<  x2 << ' ' << y2 << "\n";
     A = ans[2 * v][x1], B = ans[2 *v + 1][y1];
    nx = {all[0]}, ny = {all[0]};
    int inda = 0, indb = 0;
    for(int to : vv[v]){
        if(!to) nx.pb(A[inda]), inda++;
        else nx.pb(B[indb]), indb++;
    }
    A = ans[2 * v][x2];
    B = ans[2 * v + 1][y2];
    inda = 0, indb = 0;
    for(int to : vv[v]){
        if(!to) ny.pb(A[inda]), inda++;
        else ny.pb(B[indb]), indb++;
    }
    ans[v][c] = min(nx, ny);
    return c;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++){
        bfs(i);
    }
    int x = opt(1, a[1]);
    //cout << x << ' ';
    for(int to : ans[1][x]) 
        cout << to << ' ';
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 178744 KB Output is correct
2 Correct 79 ms 178748 KB Output is correct
3 Correct 80 ms 178764 KB Output is correct
4 Correct 80 ms 178764 KB Output is correct
5 Correct 79 ms 178712 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 178744 KB Output is correct
2 Correct 79 ms 178748 KB Output is correct
3 Correct 80 ms 178764 KB Output is correct
4 Correct 80 ms 178764 KB Output is correct
5 Correct 79 ms 178712 KB Output is correct
6 Correct 82 ms 178740 KB Output is correct
7 Correct 80 ms 178764 KB Output is correct
8 Correct 80 ms 178676 KB Output is correct
9 Correct 78 ms 178748 KB Output is correct
10 Correct 79 ms 178796 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 178744 KB Output is correct
2 Correct 79 ms 178748 KB Output is correct
3 Correct 80 ms 178764 KB Output is correct
4 Correct 80 ms 178764 KB Output is correct
5 Correct 79 ms 178712 KB Output is correct
6 Correct 82 ms 178740 KB Output is correct
7 Correct 80 ms 178764 KB Output is correct
8 Correct 80 ms 178676 KB Output is correct
9 Correct 78 ms 178748 KB Output is correct
10 Correct 79 ms 178796 KB Output is correct
11 Correct 79 ms 179020 KB Output is correct
12 Correct 82 ms 179148 KB Output is correct
13 Correct 80 ms 179024 KB Output is correct
14 Correct 89 ms 179752 KB Output is correct
15 Correct 85 ms 179720 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 178744 KB Output is correct
2 Correct 79 ms 178748 KB Output is correct
3 Correct 80 ms 178764 KB Output is correct
4 Correct 80 ms 178764 KB Output is correct
5 Correct 79 ms 178712 KB Output is correct
6 Correct 82 ms 178740 KB Output is correct
7 Correct 80 ms 178764 KB Output is correct
8 Correct 80 ms 178676 KB Output is correct
9 Correct 78 ms 178748 KB Output is correct
10 Correct 79 ms 178796 KB Output is correct
11 Correct 79 ms 179020 KB Output is correct
12 Correct 82 ms 179148 KB Output is correct
13 Correct 80 ms 179024 KB Output is correct
14 Correct 89 ms 179752 KB Output is correct
15 Correct 85 ms 179720 KB Output is correct
16 Correct 179 ms 198984 KB Output is correct
17 Correct 176 ms 198728 KB Output is correct
18 Correct 180 ms 199284 KB Output is correct
19 Runtime error 545 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 178744 KB Output is correct
2 Correct 79 ms 178748 KB Output is correct
3 Correct 80 ms 178764 KB Output is correct
4 Correct 80 ms 178764 KB Output is correct
5 Correct 79 ms 178712 KB Output is correct
6 Correct 82 ms 178740 KB Output is correct
7 Correct 80 ms 178764 KB Output is correct
8 Correct 80 ms 178676 KB Output is correct
9 Correct 78 ms 178748 KB Output is correct
10 Correct 79 ms 178796 KB Output is correct
11 Correct 79 ms 179020 KB Output is correct
12 Correct 82 ms 179148 KB Output is correct
13 Correct 80 ms 179024 KB Output is correct
14 Correct 89 ms 179752 KB Output is correct
15 Correct 85 ms 179720 KB Output is correct
16 Correct 179 ms 198984 KB Output is correct
17 Correct 176 ms 198728 KB Output is correct
18 Correct 180 ms 199284 KB Output is correct
19 Runtime error 545 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -