Submission #601386

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
using ll=long long ;

// #define DEBUG

int main(void){
	int n,m;
	cin >> n >> m;
	vector<int> x,y;

	bool tmp[3010];
	rep(i,n) tmp[i]=false;
	rep(i,m){
		int arg;
		cin >> arg;
		tmp[arg-1]=true;
	}
	
	rep(i,n) if(tmp[i]==false) x.push_back(i);

	rep(i,n) tmp[i]=false;
	rep(i,m){
		int arg;
		cin >> arg;
		tmp[arg-1]=true;
	}

	rep(i,n) if(tmp[i]==false) y.push_back(i);

	int sz=x.size();
	vector<int> xx,yy;
	rep(i,sz) xx.push_back((x[(i+1)%sz]-x[i]+n)%n);
	rep(i,sz) yy.push_back((y[(i+1)%sz]-y[i]+n)%n);

	ll ans=-1LL;

	bool can_mov=false;
	rep(i,sz) if(xx[i]>=3) can_mov=true;		

	#ifdef DEBUG
		rep(i,sz) cerr << (i?" ":"") << x[i]; 
		cerr << endl;
		rep(i,sz) cerr << (i?" ":"") << y[i];
		cerr << endl;
		cerr << endl;
	#endif

	if(sz==1){
		ll left,right;
		bool ok=true;
		if(x[0]<y[0])	
			right=y[0]-x[0],left=n+x[0]-y[0];
		else
			left=x[0]-y[0],right=n+y[0]-x[0];
		
		if(n&1){
			if(left&1) left+=n;
			if(right&1) right+=n;
		}else{
			if(left&1) ok=false;
			if(right&1) ok=false;
		}

		#ifdef DEBUG
			cerr << left << " " << right << endl;
		#endif

		if(ok&&(ans==-1||ans>abs(left/2LL))) ans=abs(left/2LL);
		if(ok&&(ans==-1||ans>abs(right/2LL))) ans=abs(right/2LL);
	
	}else{
		if(can_mov){
	
			rep(i,sz){

				bool ok=true;
				ll left,right;
				if(x[0]<y[i]) 
					right=y[i]-x[0],left=n+x[0]-y[i];
				else
					left=x[0]-y[i],right=n+y[i]-x[0];
				
				if(n&1){
					if(left&1) left+=n;
					if(right&1) right+=n;
				}else{
					if(left&1) ok=false;
					if(right&1) ok=false;
				}

				if(ok==false) continue;

				#ifdef DEBUG
					cerr << left << " " << right << endl;
				#endif

				ll cur[3010];

				// left ->
				ok=true;
				rep(j,sz) cur[j]=xx[j];

				#ifdef DEBUG
					rep(j,sz) cerr << (j?" ":"") << cur[j];
					cerr << endl;
				#endif

				ll ret=left/2LL;
				
				#ifdef DEBUG
					rep(j,sz) cerr << (j?" ":"") << cur[j];
					cerr << endl;
				#endif

				rep(j,sz-1){
					ll parity=(yy[(i+j)%sz]-cur[j])%2;
					if(parity&1) ok=false;
					ll cost=(yy[(i+j)%sz]-cur[j]);
					cur[j]+=cost,cur[(j+1)%sz]-=cost;
					ret+=abs(left/2LL-cost/2LL);
				}			

							
				#ifdef DEBUG
					rep(k,sz) cerr << (k?" ":"") << cur[k];
					cerr << endl << ret << endl;
				#endif 

				rep(j,sz) if(cur[j]!=yy[(i+j)%sz]) ok=false;
				if(ok&&(ans==-1||ans>abs(ret))) ans=abs(ret);

				// right
				ok=true;
				rep(j,sz) cur[j]=xx[j];
				ret=right/2LL;
				
				#ifdef DEBUG	
					rep(j,sz) cerr << (j?" ":"") << cur[j];
					cerr << endl;
				#endif

				rep(j,sz-1){
					ll parity=(yy[(i+j)%sz]-cur[j])%2;
					if(parity&1) ok=false;
					ll cost=(yy[(i+j)%sz]-cur[j]);
					cur[j]+=cost,cur[(j+1)%sz]-=cost;
					ret+=abs(right/2LL+cost/2);
				}

				
				#ifdef DEBUG
					rep(j,sz) cerr << (j?" ":"") << cur[j];
					cerr << endl << ret << endl << endl;
				#endif	
				rep(j,sz) if(cur[j]!=yy[(i+j)%sz]) ok=false;
				if(ok&&(ans==-1||ans>abs(ret))) ans=abs(ret);
				// cerr << lcost << " " << rcost << endl;
			}
		}
		else{
			ans=0LL;
			rep(j,sz) if(x[j]!=y[j]) ans=-1LL;  
		}
	}
	cout << ans << endl;
	return 0;
}


// oooox
// ooxoo
// xoooo

// xoooo

Submission Info

Judge Result