1183B. Circus by 李博浩

B. Circus
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
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
inputCopy
4
0011
0101
outputCopy
1 4
inputCopy
6
000000
111111
outputCopy
-1
inputCopy
4
0011
1100
outputCopy
4 3
inputCopy
8
00100101
01111100
outputCopy
1 2 3 6
Note
In the first example, one of the possible divisions into two performances is as follows: in the first performance artists 11 and 44 should take part. Then the number of artists in the first performance who can perform as clowns is equal to 11. And the number of artists in the second performance who can perform as acrobats is 11 as well.

In the second example, the division is not possible.

In the third example, one of the possible divisions is as follows: in the first performance artists 33 and 44 should take part. Then in the first performance there are 22 artists who can perform as clowns. And the number of artists in the second performance who can perform as acrobats is 22 as well.

采用枚举暴力解题
设00,01,10,11四种人数是na,nb,nc,nd
选出来的人数满足a+b+c+d=n/2
第一次表演会第一个的人数等于第二场表演会第二个的人数：c+d=nb-b+nd-d
**假设已知a，b求cd，d=nb+nd-n/2+a;c=n/2-a-b-nb-nd+n/2-a;

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> aa, bb, cc, dd;
const int N = 5001;
int n,na,nb,nc,nd;
int a[N], c[N];
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        scanf("%1d", &a[i]);
    for (int i = 0; i < n; i++)
        scanf("%1d", &c[i]);
    for (int i = 0; i < n; i++)
    {
        if (a[i] == 0 && c[i] == 0)
            na++, aa.push_back(i+1);
        else if (a[i] == 0 && c[i] == 1)
            nb++, bb.push_back(i+1);
        else if (a[i] == 1 && c[i] == 0)
            nc++, cc.push_back(i+1);
        else
            nd++, dd.push_back(i+1);
    }
    for (int a = 0; a <= na; a++)
    {
        for (int b = 0; b <= nb; b++)
        {
            int c =n-nb-nd-2*a-b;
            if (c >= 0 && c <= nc)
            {
                int d = nb+nd-n/2+a;
                if (d >= 0 && d <= nd)
                {
                    //cout << a << b << c << d << endl;
                    for (int i = 0; i < a; i++)
                        printf("%d ", aa[i]);
                    for (int i = 0; i < b; i++)
                        printf("%d ", bb[i]);
                    for (int i = 0; i < c; i++)
                        printf("%d ", cc[i]);
                    for (int i = 0; i < d; i++)
                        printf("%d ", dd[i]);
                    printf("\n");
                    return 0;
                }

            }
        }
    }
    printf("-1\n");
    return 0;
}