oj.uz

Submission #834453

# Submission time Handle Problem Language Result Execution time Memory
834453 2023-08-22T14:30:23 Z Ronin13 Swap (BOI16_swap) C++17
68 / 100
 758 ms 217552 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[100001][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 43 ms 91860 KB Output is correct
2 Correct 44 ms 91860 KB Output is correct
3 Correct 44 ms 91800 KB Output is correct
4 Correct 45 ms 91860 KB Output is correct
5 Correct 44 ms 91860 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 91860 KB Output is correct
2 Correct 44 ms 91860 KB Output is correct
3 Correct 44 ms 91800 KB Output is correct
4 Correct 45 ms 91860 KB Output is correct
5 Correct 44 ms 91860 KB Output is correct
6 Correct 45 ms 91820 KB Output is correct
7 Correct 44 ms 91860 KB Output is correct
8 Correct 45 ms 91824 KB Output is correct
9 Correct 43 ms 91852 KB Output is correct
10 Correct 46 ms 91860 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 91860 KB Output is correct
2 Correct 44 ms 91860 KB Output is correct
3 Correct 44 ms 91800 KB Output is correct
4 Correct 45 ms 91860 KB Output is correct
5 Correct 44 ms 91860 KB Output is correct
6 Correct 45 ms 91820 KB Output is correct
7 Correct 44 ms 91860 KB Output is correct
8 Correct 45 ms 91824 KB Output is correct
9 Correct 43 ms 91852 KB Output is correct
10 Correct 46 ms 91860 KB Output is correct
11 Correct 45 ms 92124 KB Output is correct
12 Correct 45 ms 92276 KB Output is correct
13 Correct 45 ms 92076 KB Output is correct
14 Correct 49 ms 92748 KB Output is correct
15 Correct 49 ms 92748 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 91860 KB Output is correct
2 Correct 44 ms 91860 KB Output is correct
3 Correct 44 ms 91800 KB Output is correct
4 Correct 45 ms 91860 KB Output is correct
5 Correct 44 ms 91860 KB Output is correct
6 Correct 45 ms 91820 KB Output is correct
7 Correct 44 ms 91860 KB Output is correct
8 Correct 45 ms 91824 KB Output is correct
9 Correct 43 ms 91852 KB Output is correct
10 Correct 46 ms 91860 KB Output is correct
11 Correct 45 ms 92124 KB Output is correct
12 Correct 45 ms 92276 KB Output is correct
13 Correct 45 ms 92076 KB Output is correct
14 Correct 49 ms 92748 KB Output is correct
15 Correct 49 ms 92748 KB Output is correct
16 Correct 143 ms 112072 KB Output is correct
17 Correct 143 ms 111948 KB Output is correct
18 Correct 142 ms 112352 KB Output is correct
19 Correct 739 ms 180540 KB Output is correct
20 Correct 758 ms 179792 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 91860 KB Output is correct
2 Correct 44 ms 91860 KB Output is correct
3 Correct 44 ms 91800 KB Output is correct
4 Correct 45 ms 91860 KB Output is correct
5 Correct 44 ms 91860 KB Output is correct
6 Correct 45 ms 91820 KB Output is correct
7 Correct 44 ms 91860 KB Output is correct
8 Correct 45 ms 91824 KB Output is correct
9 Correct 43 ms 91852 KB Output is correct
10 Correct 46 ms 91860 KB Output is correct
11 Correct 45 ms 92124 KB Output is correct
12 Correct 45 ms 92276 KB Output is correct
13 Correct 45 ms 92076 KB Output is correct
14 Correct 49 ms 92748 KB Output is correct
15 Correct 49 ms 92748 KB Output is correct
16 Correct 143 ms 112072 KB Output is correct
17 Correct 143 ms 111948 KB Output is correct
18 Correct 142 ms 112352 KB Output is correct
19 Correct 739 ms 180540 KB Output is correct
20 Correct 758 ms 179792 KB Output is correct
21 Runtime error 177 ms 217552 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -