Codeforces1138B Circus

http://codeforces.com/contest/1138/problem/B

Polycarp is a head of a circus troupe. There are nn — an even number — artists in the troupe. It is known whether the ii-th artist can perform as a clown (if yes, then ci=1ci=1, otherwise ci=0ci=0), and whether they can perform as an acrobat (if yes, then ai=1ai=1, otherwise ai=0ai=0).

Split the artists into two performances in such a way that:

  • each artist plays in exactly one performance,
  • the number of artists in the two performances is equal (i.e. equal to n2n2),
  • the number of artists that can perform as clowns in the first performance is the same as the number of artists that can perform as acrobats in the second performance.

Input

The first line contains a single integer nn (2≤n≤50002≤n≤5000, nn is even) — the number of artists in the troupe.

The second line contains nn digits c1c2…cnc1c2…cn, the ii-th of which is equal to 11 if the ii-th artist can perform as a clown, and 00 otherwise.

The third line contains nn digits a1a2…ana1a2…an, the ii-th of which is equal to 11, if the ii-th artist can perform as an acrobat, and 00 otherwise.

Output

Print n2n2 distinct integers — the indices of the artists that should play in the first performance.

If there are multiple answers, print any.

If there is no solution, print a single integer −1−1.

Examples

input

Copy

4
0011
0101

output

Copy

1 4

input

Copy

6
000000
111111

output

Copy

-1

input

Copy

4
0011
1100

output

Copy

4 3

input

Copy

8
00100101
01111100

output

Copy

1 2 3 6

 

题意:n个人,c[i]表示是否可以当小丑,a[i]表示是否可以当演员。要求选出n/2个人第一天演出,剩下的n/2个人第二天演出,使得满足:第一天可以演小丑的人的个数等于第二天可以演演员的人个数。

思路:这个题比赛时候做不出来实在是不应该。

对于任意一个人(c[i],a[i]),只有四种状态:00,01,10,11。

我们对此分类,设第一天选四种状态的人数依次是a1,a2,a3,a4;第二天选四种状态 的人数依次是b1,b2,b3,b4。

写一个双重循环枚举a3和a4,11的人数减去a4就是b4,然后就确定了b2,进而确定了b1,然后确定a1。如果这个过程中ai,bi均合法,那么找到解,结束。

#include <bits/stdc++.h>
using namespace std;

int n;
char c[6000],a[6000];
int cnt[2][2];

int main()
{
//	freopen("input.in","r",stdin);
	cin>>n;
	scanf("%s%s",c,a);
	for(int i=0;i<n;i++)cnt[c[i]-'0'][a[i]-'0']++;
	
	for(int a3=0;a3<=cnt[1][0];a3++)
	{
		for(int a4=0;a4<=cnt[1][1];a4++)
		{
			int b4=cnt[1][1]-a4;
			int b2=a3+a4-b4;
			if(b2<0||b2>cnt[0][1])continue;
			int a2=cnt[0][1]-b2;
			int a1=n/2-a2-a3-a4;
			if(a1<0||a1>cnt[0][0])continue;
			for(int i=0;i<n;i++)
			{
				if(a1&&c[i]=='0'&&a[i]=='0')printf("%d ",i+1),a1--;
				if(a2&&c[i]=='0'&&a[i]=='1')printf("%d ",i+1),a2--;
				if(a3&&c[i]=='1'&&a[i]=='0')printf("%d ",i+1),a3--;
				if(a4&&c[i]=='1'&&a[i]=='1')printf("%d ",i+1),a4--;
			}
			puts("");
			exit(0);
		}
	}
	puts("-1");
	exit(0);
}

 

全部评论

相关推荐

大方的大熊猫准备进厂:1.教育背景:你希望从事什么专业的工作你的主修课就是什么;成绩优秀是你应该做的,没什么可描述的,成绩不优秀也许人家在大学忙着创业呢?(成绩优秀不一定是好事,只能说明多元化的大学你上成了高中,没有真正上明白大学,反而体现了你死板,不爱社交,没有别的突出能力) 2.实践经历:你想表达的意思没有说清楚。你是说你会个性化服务,还是你有实习经历。如果没有带来,经济收益,表彰,更好的发展前景,那你还不如说说提升了自己哪些技能。你说有人给你送锦旗我都能明白你优秀,但是你说你会xxxx,你说这话谁信,证据呢。 3.入伍经历:你描述的就是你的工作职责或者你应该做的,并没有体现出来你把这个事情做好了,而且入伍经历并不能证明你能干好你要应聘的工作,不如只写经历其余所有内容都不写。 4.荣誉技能:重点突出一下,但不要过多描述,这些荣誉的含金量懂得都懂。 重点:你要应聘什么工作(具体岗位,实习生不具体),你的期望薪资
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务