oj.uz

Submission #834441

# Submission time Handle Problem Language Result Execution time Memory
834441 2023-08-22T14:23:59 Z Ronin13 Swap (BOI16_swap) C++17
48 / 100
 500 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][40];
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 87 ms 192876 KB Output is correct
2 Correct 84 ms 192772 KB Output is correct
3 Correct 84 ms 192888 KB Output is correct
4 Correct 90 ms 192972 KB Output is correct
5 Correct 86 ms 192880 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 192876 KB Output is correct
2 Correct 84 ms 192772 KB Output is correct
3 Correct 84 ms 192888 KB Output is correct
4 Correct 90 ms 192972 KB Output is correct
5 Correct 86 ms 192880 KB Output is correct
6 Correct 85 ms 192820 KB Output is correct
7 Correct 84 ms 192876 KB Output is correct
8 Correct 84 ms 192888 KB Output is correct
9 Correct 87 ms 192816 KB Output is correct
10 Correct 88 ms 192948 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 192876 KB Output is correct
2 Correct 84 ms 192772 KB Output is correct
3 Correct 84 ms 192888 KB Output is correct
4 Correct 90 ms 192972 KB Output is correct
5 Correct 86 ms 192880 KB Output is correct
6 Correct 85 ms 192820 KB Output is correct
7 Correct 84 ms 192876 KB Output is correct
8 Correct 84 ms 192888 KB Output is correct
9 Correct 87 ms 192816 KB Output is correct
10 Correct 88 ms 192948 KB Output is correct
11 Correct 86 ms 193104 KB Output is correct
12 Correct 86 ms 193164 KB Output is correct
13 Correct 86 ms 193124 KB Output is correct
14 Correct 90 ms 193772 KB Output is correct
15 Correct 95 ms 193716 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 192876 KB Output is correct
2 Correct 84 ms 192772 KB Output is correct
3 Correct 84 ms 192888 KB Output is correct
4 Correct 90 ms 192972 KB Output is correct
5 Correct 86 ms 192880 KB Output is correct
6 Correct 85 ms 192820 KB Output is correct
7 Correct 84 ms 192876 KB Output is correct
8 Correct 84 ms 192888 KB Output is correct
9 Correct 87 ms 192816 KB Output is correct
10 Correct 88 ms 192948 KB Output is correct
11 Correct 86 ms 193104 KB Output is correct
12 Correct 86 ms 193164 KB Output is correct
13 Correct 86 ms 193124 KB Output is correct
14 Correct 90 ms 193772 KB Output is correct
15 Correct 95 ms 193716 KB Output is correct
16 Correct 188 ms 213056 KB Output is correct
17 Correct 188 ms 213016 KB Output is correct
18 Correct 191 ms 213272 KB Output is correct
19 Runtime error 500 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 87 ms 192876 KB Output is correct
2 Correct 84 ms 192772 KB Output is correct
3 Correct 84 ms 192888 KB Output is correct
4 Correct 90 ms 192972 KB Output is correct
5 Correct 86 ms 192880 KB Output is correct
6 Correct 85 ms 192820 KB Output is correct
7 Correct 84 ms 192876 KB Output is correct
8 Correct 84 ms 192888 KB Output is correct
9 Correct 87 ms 192816 KB Output is correct
10 Correct 88 ms 192948 KB Output is correct
11 Correct 86 ms 193104 KB Output is correct
12 Correct 86 ms 193164 KB Output is correct
13 Correct 86 ms 193124 KB Output is correct
14 Correct 90 ms 193772 KB Output is correct
15 Correct 95 ms 193716 KB Output is correct
16 Correct 188 ms 213056 KB Output is correct
17 Correct 188 ms 213016 KB Output is correct
18 Correct 191 ms 213272 KB Output is correct
19 Runtime error 500 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -