提出 #34046642

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef pair<ld,ld> state;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
const int DEBUG=0;
int a[222222];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	for(int cc=1;;cc++)
	{
		int n; 
		if(DEBUG) n=100;
		else cin>>n;
		vi vec;
		
		if(DEBUG)
		{
			for(int i=0;i<2*n;i++) vec.pb(i);
			random_shuffle(vec.begin(),vec.end());
			for(int i=0;i<2*n;i++) a[i]=vec[i];		
		}
		else
		{
			for(int i=0;i<2*n;i++) cin>>a[i];
		}
		vi ans;
		for(int i=1;i+1<2*n;i+=2) //a[i-1],a[i],a[i+1]
		{
			if(i%2==1) //max
			{
				if(a[i]==max(a[i],max(a[i-1],a[i+1]))) continue;
				if(a[i-1]>a[i+1])
				{
					swap(a[i-1],a[i]); ans.pb(i-1);
				}
				else
				{
					swap(a[i+1],a[i]); ans.pb(i);
				}
			}
			else //min
			{
				if(a[i]==min(a[i],min(a[i-1],a[i+1]))) continue;
				if(a[i-1]<a[i+1])
				{
					swap(a[i-1],a[i]); ans.pb(i-1);
				}
				else
				{
					swap(a[i+1],a[i]); ans.pb(i);
				}
			}
		}
		for(int i=2;i+1<2*n;i+=2) //a[i-1],a[i],a[i+1]
		{
			if(i%2==1) //max
			{
				if(a[i]==max(a[i],max(a[i-1],a[i+1]))) continue;
				if(a[i-1]>a[i+1])
				{
					swap(a[i-1],a[i]); ans.pb(i-1);
				}
				else
				{
					swap(a[i+1],a[i]); ans.pb(i);
				}
			}
			else //min
			{
				if(a[i]==min(a[i],min(a[i-1],a[i+1]))) continue;
				if(a[i-1]<a[i+1])
				{
					swap(a[i-1],a[i]); ans.pb(i-1);
				}
				else
				{
					swap(a[i+1],a[i]); ans.pb(i);
				}
			}
		}
		//check last 2
		if(a[2*n-2]>a[2*n-1]) 
		{
			swap(a[2*n-2],a[2*n-1]); ans.pb(2*n-2);
		}
		for(int i=0;i+1<2*n;i++)
		{
			if(i%2==0) assert(a[i]<a[i+1]);
			else assert(a[i]>a[i+1]);
		}
		assert(int(ans.size())<=n);
		if(!DEBUG)
		{
			cout<<ans.size()<<'\n';
			for(auto x:ans)
			{
				cout<<x+1<<' ';
			}
			cout<<'\n';
			return 0;
		}
		cerr<<"Case #"<<cc<<" complete\n";
	}
}

提出情報

ジャッジ結果