oj.uz

Submission #834450

# Submission time Handle Problem Language Result Execution time Memory
834450 2023-08-22T14:29:15 Z Ronin13 Swap (BOI16_swap) C++17
68 / 100
 728 ms 133904 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 = 50001;

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 21 ms 44884 KB Output is correct
2 Correct 20 ms 44884 KB Output is correct
3 Correct 27 ms 44952 KB Output is correct
4 Correct 22 ms 44884 KB Output is correct
5 Correct 21 ms 44884 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 44884 KB Output is correct
2 Correct 20 ms 44884 KB Output is correct
3 Correct 27 ms 44952 KB Output is correct
4 Correct 22 ms 44884 KB Output is correct
5 Correct 21 ms 44884 KB Output is correct
6 Correct 20 ms 44952 KB Output is correct
7 Correct 20 ms 44916 KB Output is correct
8 Correct 24 ms 44964 KB Output is correct
9 Correct 23 ms 44884 KB Output is correct
10 Correct 22 ms 44884 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 44884 KB Output is correct
2 Correct 20 ms 44884 KB Output is correct
3 Correct 27 ms 44952 KB Output is correct
4 Correct 22 ms 44884 KB Output is correct
5 Correct 21 ms 44884 KB Output is correct
6 Correct 20 ms 44952 KB Output is correct
7 Correct 20 ms 44916 KB Output is correct
8 Correct 24 ms 44964 KB Output is correct
9 Correct 23 ms 44884 KB Output is correct
10 Correct 22 ms 44884 KB Output is correct
11 Correct 23 ms 45140 KB Output is correct
12 Correct 24 ms 45268 KB Output is correct
13 Correct 23 ms 45140 KB Output is correct
14 Correct 27 ms 45780 KB Output is correct
15 Correct 29 ms 45780 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 44884 KB Output is correct
2 Correct 20 ms 44884 KB Output is correct
3 Correct 27 ms 44952 KB Output is correct
4 Correct 22 ms 44884 KB Output is correct
5 Correct 21 ms 44884 KB Output is correct
6 Correct 20 ms 44952 KB Output is correct
7 Correct 20 ms 44916 KB Output is correct
8 Correct 24 ms 44964 KB Output is correct
9 Correct 23 ms 44884 KB Output is correct
10 Correct 22 ms 44884 KB Output is correct
11 Correct 23 ms 45140 KB Output is correct
12 Correct 24 ms 45268 KB Output is correct
13 Correct 23 ms 45140 KB Output is correct
14 Correct 27 ms 45780 KB Output is correct
15 Correct 29 ms 45780 KB Output is correct
16 Correct 125 ms 65096 KB Output is correct
17 Correct 122 ms 64988 KB Output is correct
18 Correct 125 ms 65352 KB Output is correct
19 Correct 725 ms 133904 KB Output is correct
20 Correct 728 ms 133064 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 44884 KB Output is correct
2 Correct 20 ms 44884 KB Output is correct
3 Correct 27 ms 44952 KB Output is correct
4 Correct 22 ms 44884 KB Output is correct
5 Correct 21 ms 44884 KB Output is correct
6 Correct 20 ms 44952 KB Output is correct
7 Correct 20 ms 44916 KB Output is correct
8 Correct 24 ms 44964 KB Output is correct
9 Correct 23 ms 44884 KB Output is correct
10 Correct 22 ms 44884 KB Output is correct
11 Correct 23 ms 45140 KB Output is correct
12 Correct 24 ms 45268 KB Output is correct
13 Correct 23 ms 45140 KB Output is correct
14 Correct 27 ms 45780 KB Output is correct
15 Correct 29 ms 45780 KB Output is correct
16 Correct 125 ms 65096 KB Output is correct
17 Correct 122 ms 64988 KB Output is correct
18 Correct 125 ms 65352 KB Output is correct
19 Correct 725 ms 133904 KB Output is correct
20 Correct 728 ms 133064 KB Output is correct
21 Runtime error 117 ms 119512 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -