Submission #1305420

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
template<class T>bool chmin(T&a,const T&b){return a>b?(a=b,true):false;}
template<class T>bool chmax(T&a,const T&b){return a<b?(a=b,true):false;}

int nextInt() { int x; scanf("%d", &x); return x;}

const int MAX_N = 100000 + 10;
int A[MAX_N];
int Aorg[MAX_N];
int B[MAX_N];
int tmp[MAX_N];

// 内部的には 1-based であるが、利用するときには 0-based な実装
struct BIT {
  int n;
  vector<ll> tree;
  BIT(int n):n(n),tree(n+1) {} 
  void fill(ll val) {
    REP(i, n+1) tree[i] = (i&-i) * val;
  }
  void add(int idx, ll val) {
    for (int x=idx+1; x<=n; x+=x&-x) tree[x] += val;
  }
  ll range(int idx) {
    ll sum=0;
    for (int x=idx+1; x>0; x-=x&-x) sum += tree[x];
    return sum;
  }
  ll range(int a, int b) {
    return range(b) - range(a - 1);
  }
};


ll count_reverse_num(int* a, int N) {
  ll ans = 0;
  BIT bit(N);
  REP(i, N) {
    ans += i - bit.range(a[i]);
    bit.add(a[i], +1);
  }
  return ans;
}

void renumber(int *A, int *T, int N) {
  REP(i, N) tmp[T[i]] = i;
  REP(i, N) A[i] = tmp[A[i]];
}
void renumber_inv(int *A, int *T, int N) {
  REP(i, N) tmp[i] = T[i];
  REP(i, N) A[i] = tmp[A[i]];
}

int main2() {
  int N = nextInt();
  REP(i, N) A[i] = nextInt() - 1;
  REP(i, N) B[i] = nextInt() - 1;
  REP(i, N) Aorg[i] = A[i];

  // renumber(A, Aorg, N);
  renumber(B, Aorg, N);

  int bb = count_reverse_num(B, N);
  if (bb % 2 == 1) {
    cout << -1 << endl;
  } else {
    bb /= 2;

    // // O(N^2) 解法
    // for (int i = 0; i < N; i++) {
    //   for (int j = N - 1; j > i; j--) {
    //     if (B[j-1] > B[j]) {
    //       swap(B[j-1], B[j]);
    //       bb--;
    //       if (bb == 0) goto BK;
    //     }
    //   }
    // }
    // BK:

    BIT bit(N+1);
    
    int sz = 0;
    for (int i = 0; i < N; i++) {
      int g = bit.range(N - B[i]);
      if (g <= bb) {
        bb -= g;
        sz++;
        bit.add(N - B[i], +1);
      } else {
        break;
      }
    }
    sort(B, B + sz);

    for (int i = 0; i < N && bb > 0; i++) {
      for (int j = N - 1; j > i && bb > 0; j--) {
        if (B[j-1] > B[j]) {
          swap(B[j-1], B[j]);
          bb--;
        }
      }
    }

    renumber_inv(B, Aorg, N);
    REP(i, N) { if (i > 0)  cout << " "; cout << (B[i] + 1); } cout << endl;
  }
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws) main2();
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int nextInt()’:
./Main.cpp:9:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 int nextInt() { int x; scanf("%d", &x); return x;}
                                       ^

Judge Result