Submission #1156082
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif
const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
os << "[";
for (const auto &v : vec) {
os << v << ",";
}
os << "]";
return os;
}
using i64=int64_t;
template<class T,T op(T,T)> class segtree{
public:
int n,size_;
vector<T> dat;
T id_;
segtree()=default;
segtree(int size,T id,T initial_value){ init(size,id,initial_value); }
void init(int size,T id,T initial_value){
size_=size;
id_=id;
n=1;
while(n<size) n*=2;
dat.assign(2*n-1,id);
for(int i=0; i<size; ++i) update(i,initial_value);
}
int size()const{ return size_; }
void update(int k, T a) {
k+=n-1; // leaf
dat[k]=a;
while(k>0) {
k=(k-1)/2;
dat[k]=op(dat[k*2+1],dat[k*2+2]);
}
}
T at(int index){ return dat[index+n-1]; }
void add(int k,T a){ update(k,op(at(k),a)); }
T query(int a,int b) { return query(a,b,0,0,n); }
T query(int a,int b,int k,int l,int r) {
if(r<=a or b<=l) return id_;
if(a<=l and r<=b) return dat[k];
int m=(l+r)/2;
return op(query(a,b,k*2+1,l,m),query(a,b,k*2+2,m,r));
}
};
int add(int a,int b){
return a+b;
}
void solve(){
int n;
cin >> n;
vector<int> a(n),b(n),f(n),g(n);
rep(i,0,n){
cin >> a[i];
--a[i];
f[a[i]]=i;
g[i]=a[i];
a[i]=i;
}
rep(i,0,n){
cin >> b[i];
--b[i];
b[i]=f[b[i]];
}
i64 d=0;
segtree<int,add> seg(n,0,0);
rep(i,0,n){
d+=i-seg.query(0,b[i]);
seg.update(b[i],1);
}
if(d==0 or d%2==1){
cout << -1 << endl;
return;
}
i64 d_=0;
seg.init(n,0,0);
rep(i,0,n){
i64 tmp=i-seg.query(0,b[i]);
if(d_+tmp>=d/2){
sort(b.begin(),b.begin()+i);
for(int j=i; j>0; --j){
if(b[j]<b[j-1]){
swap(b[j],b[j-1]);
++d_;
if(d_==d/2){
rep(k,0,n) cout << g[b[k]]+1 << (k==n-1?'\n':' ');
return;
}
}
}
}
d_+=tmp;
seg.update(b[i],1);
}
}
int main(){
std::cin.tie(0);
std::ios::sync_with_stdio(false);
cout.setf(ios::fixed);
cout.precision(10);
solve();
return 0;
}
Submission Info
Submission Time |
|
Task |
C - 転倒距離 |
User |
walkre |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2884 Byte |
Status |
AC |
Exec Time |
66 ms |
Memory |
3456 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
30 / 30 |
70 / 70 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
Subtask1 |
sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt |
Subtask2 |
sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
subtask1_01.txt |
AC |
2 ms |
384 KB |
subtask1_02.txt |
AC |
3 ms |
384 KB |
subtask1_03.txt |
AC |
2 ms |
256 KB |
subtask1_04.txt |
AC |
2 ms |
256 KB |
subtask1_05.txt |
AC |
2 ms |
256 KB |
subtask1_06.txt |
AC |
1 ms |
256 KB |
subtask1_07.txt |
AC |
2 ms |
256 KB |
subtask1_08.txt |
AC |
1 ms |
256 KB |
subtask1_09.txt |
AC |
2 ms |
384 KB |
subtask1_10.txt |
AC |
2 ms |
256 KB |
subtask1_11.txt |
AC |
2 ms |
384 KB |
subtask1_12.txt |
AC |
2 ms |
256 KB |
subtask1_13.txt |
AC |
2 ms |
256 KB |
subtask1_14.txt |
AC |
2 ms |
384 KB |
subtask1_15.txt |
AC |
2 ms |
384 KB |
subtask1_16.txt |
AC |
3 ms |
384 KB |
subtask1_17.txt |
AC |
2 ms |
384 KB |
subtask1_18.txt |
AC |
3 ms |
384 KB |
subtask1_19.txt |
AC |
3 ms |
384 KB |
subtask2_01.txt |
AC |
6 ms |
640 KB |
subtask2_02.txt |
AC |
51 ms |
2944 KB |
subtask2_03.txt |
AC |
60 ms |
3200 KB |
subtask2_04.txt |
AC |
21 ms |
1664 KB |
subtask2_05.txt |
AC |
29 ms |
2432 KB |
subtask2_06.txt |
AC |
17 ms |
1536 KB |
subtask2_07.txt |
AC |
32 ms |
2560 KB |
subtask2_08.txt |
AC |
61 ms |
3328 KB |
subtask2_09.txt |
AC |
21 ms |
1664 KB |
subtask2_10.txt |
AC |
19 ms |
1536 KB |
subtask2_11.txt |
AC |
27 ms |
1664 KB |
subtask2_12.txt |
AC |
37 ms |
2816 KB |
subtask2_13.txt |
AC |
65 ms |
3456 KB |
subtask2_14.txt |
AC |
34 ms |
2688 KB |
subtask2_15.txt |
AC |
66 ms |
3456 KB |
subtask2_16.txt |
AC |
66 ms |
3456 KB |
subtask2_17.txt |
AC |
66 ms |
3456 KB |
subtask2_18.txt |
AC |
66 ms |
3456 KB |
subtask2_19.txt |
AC |
65 ms |
3456 KB |