oj.uz

Submission #833937

# Submission time Handle Problem Language Result Execution time Memory
833937 2023-08-22T09:37:48 Z Ronin13 Swap (BOI16_swap) C++17
0 / 100
 6 ms 12836 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 <bool> vv[nmax];
vector <vector <int> > g(nmax);
int a[nmax];
void bfs(int x){
    queue <pii> q;
    for(int i = 0; i < g[x].size(); i++){
        q.push({g[x][i], i});
    }
    while(!q.empty()){
        int v = q.front().f;
        vv[x].pb(q.front().s);
        q.pop();
        for(int to : g[v]){
            q.push({to, vv[x].back()});
        }
    }
}

map <pii, vector <int> > ans;

vector <int> opt(int v, int x){
    if(!ans[{v, x}].empty()) return ans[{v, x}];
    if(g[v].empty()){
        return ans[{v, x}] = {x};
    }
    if(g[v].size() == 1){
        int y = g[v][0];
        if(a[y] < x){
            return ans[{v, x}] = {a[y], x};
        }
        return ans[{v, x}] = {x, a[y]};
    }
    vector <int> A, B, C, D;
    vector <int> all;
    all.pb(x);
    for(int to : g[v]){
        all.pb(a[to]);
    }
    sort(all.begin(), all.end());
    vector <int> nx, ny;
    nx.pb(all[0]), ny.pb(all[0]);
    if(all[0] == x){
        A = opt(g[v][0], a[g[v][0]]);
        B = opt(g[v][1], a[g[v][1]]);
       int inda = 0, indb = 0;
        for(auto to : vv[v]){
        if(!to) nx.pb(A[inda++]);
        else nx.pb(B[indb++]);
        }
        return ans[{v, x}] = nx;
    }
    A = opt(g[v][0], all[2]), B = opt(g[v][1], all[1]);
    C = opt(g[v][0], all[1]); D = opt(g[v][1], all[2]);
    int inda = 0, indb = 0;
    for(auto to : vv[v]){
        if(!to) nx.pb(A[inda++]);
        else nx.pb(B[indb++]);
    }
    inda = indb = 0;
    for(auto to : vv[v]){
        if(!to) ny.pb(C[inda++]);
        else ny.pb(D[indb++]);
    }
    return ans[{v, x}] = min(nx, ny);
}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        if(i * 2 <= n)g[i].pb(i * 2);
        if(i *2  + 1<= n) g[i].pb(i * 2 + 1);
    }
    for(int i = 1; i <= n; i++)
        bfs(i);
    vector <int> op = opt(1, a[1]);
    for(int to : op){
        cout << to << ' ';
    }
    return 0;
}

Compilation message

swap.cpp: In function 'void bfs(int)':
swap.cpp:19:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int i = 0; i < g[x].size(); i++){
      |                    ~~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12836 KB Output is correct
2 Incorrect 6 ms 12756 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12836 KB Output is correct
2 Incorrect 6 ms 12756 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12836 KB Output is correct
2 Incorrect 6 ms 12756 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12836 KB Output is correct
2 Incorrect 6 ms 12756 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12836 KB Output is correct
2 Incorrect 6 ms 12756 KB Output isn't correct
3 Halted 0 ms 0 KB -