oj.uz

Submission #834481

# Submission time Handle Problem Language Result Execution time Memory
834481 2023-08-22T14:48:32 Z Ronin13 Swap (BOI16_swap) C++17
0 / 100
 13 ms 20564 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[200001];
unordered_map <int, int> mp[200001];
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){
    ans[v].clear();
   
    if(2 * v > n){
        ans[v] = {x};
        return 1;
    }
    if(2 * v + 1 > n){
        if(a[2 * v] > x)
            ans[v] = {x, a[2 * v]};
        else ans[v] = {a[2 * v], x};
        return 1;
    }
    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];
        B = ans[2 * v + 1];
        ans[v].pb(x);
        int inda, indb;
        inda = indb = 0;
        for(int to : vv[v]){
            if(!to) ans[v].pb(A[inda]), inda++;
            else ans[v].pb(B[indb]), indb++;
        }
        return 1;
    }
    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];
        B = ans[2 * v + 1];
        ans[v].pb(a[2 * v]);
        int inda, indb;
        inda = indb = 0;
        for(int to : vv[v]){
            if(!to) ans[v].pb(A[inda]), inda++;
            else ans[v].pb(B[indb]), indb++;
        }
        return 1;
    }
    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], B = ans[2 *v + 1];
    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];
    B = ans[2 * v + 1];
    inda = 0, indb = 0;
    for(int to : vv[v]){
        if(!to) ny.pb(A[inda]), inda++;
        else ny.pb(B[indb]), indb++;
    }
    ans[v] = min(nx, ny);
    return 1;
}

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);
        ans[i].pb({});
    }
    int x = opt(1, a[1]);
    //cout << x << ' ';
    for(int to : ans[1]) 
        cout << to << ' ';
    return 0;
}

Compilation message

swap.cpp: In function 'int opt(int, int)':
swap.cpp:58:13: warning: unused variable 'xx' [-Wunused-variable]
   58 |         int xx = opt(2 * v, a[2 * v]);
      |             ^~
swap.cpp:59:13: warning: unused variable 'yy' [-Wunused-variable]
   59 |         int yy =  opt(2 * v+  1, a[ 2* v + 1]);
      |             ^~
swap.cpp:72:13: warning: unused variable 'xx' [-Wunused-variable]
   72 |         int xx = opt(2 * v, x);
      |             ^~
swap.cpp:73:13: warning: unused variable 'yy' [-Wunused-variable]
   73 |         int yy = opt(2 * v + 1, a[2 * v + 1]);
      |             ^~
swap.cpp:85:9: warning: unused variable 'x1' [-Wunused-variable]
   85 |     int x1 = opt(2 * v, all[1]), y1 = opt(2 * v+ 1, all[2]);
      |         ^~
swap.cpp:85:34: warning: unused variable 'y1' [-Wunused-variable]
   85 |     int x1 = opt(2 * v, all[1]), y1 = opt(2 * v+ 1, all[2]);
      |                                  ^~
swap.cpp:86:9: warning: unused variable 'x2' [-Wunused-variable]
   86 |     int x2 = opt(2 * v, all[2]), y2 = opt(2 * v+ 1, all[1]);
      |         ^~
swap.cpp:86:34: warning: unused variable 'y2' [-Wunused-variable]
   86 |     int x2 = opt(2 * v, all[2]), y2 = opt(2 * v+ 1, all[1]);
      |                                  ^~
swap.cpp: In function 'int main()':
swap.cpp:116:9: warning: unused variable 'x' [-Wunused-variable]
  116 |     int x = opt(1, a[1]);
      |         ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 20564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 20564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 20564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 20564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 20564 KB Output isn't correct
2 Halted 0 ms 0 KB -