Submission #1177591

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define rep(i,n) FOR(i,0,n)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define vint vector<int>
#define vdouble vector<double>
#define vstring vector<string>
using namespace std;

#include<map>
#include<set>
#include<queue>

typedef long long ll;
typedef unsigned long long ull;

const int MAX_N = 1000000;
int N;

int A[100000], B[100000], M[100000], BB[100000], M2[100000];
ll ct;

void merge(int n[], int left, int mid, int right, ll mx)
{
    int num = right - left;
    int *tmp = new int[num];

    int iw = 0;
    int il = left;
    int ir = mid;

    while (il < mid && ir < right)
    {
        ll ctp = mid - il;
        if (n[il] <= n[ir] || mx < ct + ctp)
        {
            tmp[iw++] = n[il++];
        }
        else
        {
            tmp[iw++] = n[ir++];
            ct += ctp;
        }
    }

    while (il < mid) tmp[iw++] = n[il++];
    while (ir < right) tmp[iw++] = n[ir++];

    for (int i=0; i<num; i++) n[left + i] = tmp[i];

    delete[] tmp;

}


void merge_sort_sub(int n[], int left, int right, ll mx)
{
    if (right - left <= 1) return;

    int mid = left + (right - left) / 2;
    merge_sort_sub(n, left, mid, mx);
    merge_sort_sub(n, mid, right, mx);
    merge(n, left, mid, right, mx);

}

int main() {
    cin >> N;
    rep(i, N){ cin >> A[i]; A[i]--; }
    rep(i, N){ cin >> B[i]; B[i]--; }

    // mapping
    rep(i, N){ M[A[i]] = i; }
    rep(i, N){ M2[M[i]] = i; }

    rep(i, N){ A[i] = M[A[i]]; }
    rep(i, N){ B[i] = M[B[i]]; }
    rep(i, N){ BB[i] = B[i];}

    cerr << "M : "; rep(i, N){ cerr << M[i] << " ";} cerr << endl;
    cerr << "M2: "; rep(i, N){ cerr << M2[i] << " ";} cerr << endl;
    cerr << "AM: "; rep(i, N){ cerr << A[i] << " ";} cerr << endl;
    cerr << "BM: "; rep(i, N){ cerr << B[i] << " ";} cerr << endl;
    cerr << "A : "; rep(i, N){ cerr << M2[A[i]]+1 << " ";} cerr << endl;
    cerr << "B : "; rep(i, N){ cerr << M2[B[i]]+1 << " ";} cerr << endl;

    ct = 0;
    merge_sort_sub(BB, 0, N, INT64_MAX);
    ll cross = ct;
    cerr << "cross:" << cross << endl;

    if(cross %2 != 0) {cout << -1 << endl; return 0;}

    ct = 0;
    merge_sort_sub(B, 0, N, cross/2);

    cerr << "BH: ";
    rep(i, N){ cerr << B[i] << " ";}
    cerr << endl;


    // answer
    rep(i, N){ cout << M2[B[i]]+1 << " ";} cout << endl;
}

Submission Info

Judge Result