Submission #1305363

---

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 {
    // O(N^2) 解法
    for (int i = N; i > 0; i--) {
      for (int j = i - 1; j > 0; j--) {
        if (B[j-1] < B[j] && bb > 0) {
          swap(B[j-1], B[j]);
          bb--;
          if (bb == 0) goto BK;
        }
      }
    }

    BK:
    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