Submission #9574857

---

Source Code Expand

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx") 
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define F2(i,a,b) for(int i=(a);i<(b);++i)
#define dF(i,a,b) for(int i=(a);i>=(b);--i)
#define dF2(i,a,b) for(int i=(a);i>(b);--i)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define INF 999999
#define INFll 0x3f3f3f3f3f3f3f3f
#define y0 _lxybz_
#define y1 _ljmnzyzhhhoscartxdy_
typedef long double ld;
typedef long long ll;
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize
#define lo(x) ((x)&(-(x)))
#define trav(a, x) for (auto &a : x)
//typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
const ld Pi = 4*atan((ld)1);
template<class T> void chmin(T &a,const T&b) { a = min(a, b); }
template<class T> void chmax(T &a,const T&b) { a = max(a, b); }
namespace IO{
template<class T> inline void read(T&ret)
{
	ret=0; int f=1; char c=getchar();
	while(c<48||c>57){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>=48 && c<=57)ret=ret*10+c-48,c=getchar();
	ret*=f;
}
template<class T> inline void prin(const T&ret)
{
	if(!ret){putchar(48);return;} static T o; o=ret;
	if(o<0){putchar('-');o=-o;}
	static int op[25],tt; tt=0;
	while(o){
		op[++tt]=o%10;
		o/=10;
	}
	for(int i=tt;i;--i)putchar(op[i]+48);
}
template<class T> inline void pri_(const T&ret)
{
	prin(ret);putchar(' ');
}
template<class T> inline void priE(const T&ret)
{
	prin(ret);putchar('\n');
}
}
using namespace IO;

#define N 300005
//#define MO 
int h[N][20],vi[N][20],O,n,a[20],b[20],Ans;
int dfs(int p, int op, int la)
{
	
	if(op==3)
	int lxy=1;
	
	if(vi[op][la])return h[op][la];
	vi[op][la]=1;
	if(!p)return h[op][la]=0;
	h[op][la]=INF;
	int w,pp,ss,_ss=0,_w;
	if(abs(la-p)&1)w=b[la];else w=a[la];
	pp=op^(1<<la);
	F2(i,la+1,n)if(pp&(1<<i))++_ss;
	F2(i,0,n)if(pp&(1<<i)){
		if(abs(i-p)&1)_w=a[i];else _w=b[i];
		if(_w>w)continue;
		ss=dfs(p-1,pp,i)+_ss;
		chmin(h[op][la],ss);
	}
	return h[op][la];
}

inline void _Sol_()
{
	read(n);F2(i,0,n)read(a[i]);F2(i,0,n)read(b[i]);
	O=(1<<n)-1;
//	F(o,1,O)_[o]=_[o>>1]+(o&1);
//	F(o,0,O)G[_[o]].push_back(o);
	Ans=INF;
	F2(i,0,n)
	dfs(n-1,O,i),
	chmin(Ans,h[O][i]);
	if(Ans>10000)prin(-1);else prin(Ans); //01 020  scanf 020
}

int main()
{
	int T=1; //read(T);
	while(T--)_Sol_();
}
/*
3
3 4 3
3 2 3
*/

Submission Info

Judge Result