oj.uz

Submission #834442

# Submission time Handle Problem Language Result Execution time Memory
834442 2023-08-22T14:25:16 Z Ronin13 Swap (BOI16_swap) C++17
48 / 100
 632 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][36];
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()});
        }

    }
}

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]);
        vector <int> A = ans[2 * v][xx];
        vector <int> 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]);
        vector <int> A = ans[2 * v][xx];
        vector <int> 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";
    vector <int> A = ans[2 * v][x1], B = ans[2 *v + 1][y1];
    vector <int> 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 79 ms 173980 KB Output is correct
2 Correct 77 ms 174132 KB Output is correct
3 Correct 78 ms 174096 KB Output is correct
4 Correct 79 ms 174100 KB Output is correct
5 Correct 80 ms 173968 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 173980 KB Output is correct
2 Correct 77 ms 174132 KB Output is correct
3 Correct 78 ms 174096 KB Output is correct
4 Correct 79 ms 174100 KB Output is correct
5 Correct 80 ms 173968 KB Output is correct
6 Correct 76 ms 174016 KB Output is correct
7 Correct 78 ms 173992 KB Output is correct
8 Correct 77 ms 174100 KB Output is correct
9 Correct 76 ms 174108 KB Output is correct
10 Correct 79 ms 173988 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 173980 KB Output is correct
2 Correct 77 ms 174132 KB Output is correct
3 Correct 78 ms 174096 KB Output is correct
4 Correct 79 ms 174100 KB Output is correct
5 Correct 80 ms 173968 KB Output is correct
6 Correct 76 ms 174016 KB Output is correct
7 Correct 78 ms 173992 KB Output is correct
8 Correct 77 ms 174100 KB Output is correct
9 Correct 76 ms 174108 KB Output is correct
10 Correct 79 ms 173988 KB Output is correct
11 Correct 80 ms 174404 KB Output is correct
12 Correct 79 ms 174416 KB Output is correct
13 Correct 78 ms 174284 KB Output is correct
14 Correct 83 ms 174924 KB Output is correct
15 Correct 83 ms 174976 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 173980 KB Output is correct
2 Correct 77 ms 174132 KB Output is correct
3 Correct 78 ms 174096 KB Output is correct
4 Correct 79 ms 174100 KB Output is correct
5 Correct 80 ms 173968 KB Output is correct
6 Correct 76 ms 174016 KB Output is correct
7 Correct 78 ms 173992 KB Output is correct
8 Correct 77 ms 174100 KB Output is correct
9 Correct 76 ms 174108 KB Output is correct
10 Correct 79 ms 173988 KB Output is correct
11 Correct 80 ms 174404 KB Output is correct
12 Correct 79 ms 174416 KB Output is correct
13 Correct 78 ms 174284 KB Output is correct
14 Correct 83 ms 174924 KB Output is correct
15 Correct 83 ms 174976 KB Output is correct
16 Correct 180 ms 193992 KB Output is correct
17 Correct 179 ms 193920 KB Output is correct
18 Correct 191 ms 194308 KB Output is correct
19 Runtime error 632 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 79 ms 173980 KB Output is correct
2 Correct 77 ms 174132 KB Output is correct
3 Correct 78 ms 174096 KB Output is correct
4 Correct 79 ms 174100 KB Output is correct
5 Correct 80 ms 173968 KB Output is correct
6 Correct 76 ms 174016 KB Output is correct
7 Correct 78 ms 173992 KB Output is correct
8 Correct 77 ms 174100 KB Output is correct
9 Correct 76 ms 174108 KB Output is correct
10 Correct 79 ms 173988 KB Output is correct
11 Correct 80 ms 174404 KB Output is correct
12 Correct 79 ms 174416 KB Output is correct
13 Correct 78 ms 174284 KB Output is correct
14 Correct 83 ms 174924 KB Output is correct
15 Correct 83 ms 174976 KB Output is correct
16 Correct 180 ms 193992 KB Output is correct
17 Correct 179 ms 193920 KB Output is correct
18 Correct 191 ms 194308 KB Output is correct
19 Runtime error 632 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -