POJ2454 Jersey Politics

何でもいいから解を一つ求めればいいので、適当に山登り&登りきれなかったらrandom_shuffleで適当に書く。通る。(多分嘘解法じゃないはず)

K<=60をK<=20だと思っていて半分全列挙書いて配列外参照でREしてたのは内緒。

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<stdlib.h>
using namespace std;
typedef pair<int,int>pii;
int main()
{
	int num;
	scanf("%d",&num);
	vector<pii>vec;
	for(int i=0;i<3*num;i++)
	{
		int zan;
		scanf("%d",&zan);
		vec.push_back(make_pair(zan,i+1));
	}
	sort(vec.begin(),vec.end());
	reverse(vec.begin(),vec.end());
	for(;;)
	{
		vector<int>a,b;
		int asum=0,bsum=0;
		for(int i=0;i<num;i++)
		{
			a.push_back(i);
			asum+=vec[i].first;
		}
		for(int j=0;j<num;j++)
		{
			b.push_back(j+num);
			bsum+=vec[j+num].first;
		}
		int han=0;
		for(;;)
		{
			if(asum>num*500&&bsum>num*500)
			{
				for(int i=0;i<num;i++)
				{
					printf("%d\n",vec[a[i]].second);
				}
				for(int i=0;i<num;i++)
				{
					printf("%d\n",vec[b[i]].second);
				}
				for(int i=0;i<num;i++)
				{
					printf("%d\n",vec[i+num+num].second);
				}
				return 0;
			}
			int mini=10000000;
			int sa,sb;
			for(int i=0;i<num;i++)
			{
				for(int j=0;j<num;j++)
				{
					if(mini>abs((asum-a[i]-a[i]+b[j]+b[j]-bsum)))
					{
						sa=i;
						sb=j;
					}
				}
			}
			if(mini==10000000)
			{
				han=1;
			}
			if(han==1)
			{
				random_shuffle(vec.begin(),vec.begin()+2*num);
				break;
			}
			asum-=a[sa];
			bsum-=b[sb];
			asum+=b[sb];
			bsum+=a[sa];
			swap(a[sa],b[sb]);
		}
	}
}