Bài B - Codeforces Round #545 (Div.2)

Bài B:
Đề bài: Polycarp là người đứng đầu đoàn xiếc. Có n (n chẵn) nghệ sĩ trong đoàn xiếc. Được biết, nghệ sĩ thứ i có thể biểu diễn như một chú hề (nếu có, thì c(i)=1, ngược lại c(i)=0) và liệu họ có thể thực hiện như một acrobat (nếu có, thì a(i)=1, ngược lại a(i)=0).
Chia các nghệ sĩ thành 2 buổi biểu diễn theo cách sau đây:
+ mỗi nghệ sĩ đóng chính xác 1 buổi biểu diễn.
+ số lượng nghệ sĩ ở trong 2 buổi biểu diễn bằng nhau (tức là đều bằng n/2).
+ số lượng nghệ sĩ có thể biểu diễn như 1 chú hề trong buổi biểu diễn thứ nhất bằng với số lượng nghệ sĩ biểu diễn như 1 acrobats ở buổi biểu diễn thứ 2.
Đầu vào:
+ Dòng đầu tiên chứa số nguyên n (2<=n<=5000, n là số chẵn) - là số nghệ sĩ trong đoàn xiếc.
+ Dòng thứ hai chứa n chữ số c(1),c(2),...,c(n) - với c(i)=1 khi người thứ i là chú hề và c(i)=0 trong trường hợp ngược lại.
+ Dòng thứ ba chứa n chữ số a(1),a(2),...,a(n) - với a(i)=1 khi người thứ i là acrobat và a(i)=0 trong trường hợp ngược lại.
Đầu ra:
+ In ra n/2 số nguyên - là chỉ số các nghệ sĩ sẽ đóng kịch ở buổi biểu diễn đầu tiên.
Nếu có nhiều câu trả lời, in ra đáp án bất kỳ.
Nếu không có nghiệm nào, in ra -1.
Ví dụ:
Đầu vào:
0011
0101
Đầu ra:
1 4
/**/
Đầu vào:
6
000000
111111
Đầu ra:
-1
/**/
Đầu vào:
4
0011
1100
Đầu ra:
4 3
/**/
Đầu vào:
8
00100101
01111100
Đầu ra:
1 2 3 6
Chú thích:
 Ở ví dụ đầu tiên, một trong những các chia hợp lý thành 2 buổi biểu diễn như sau: Ở buổi biểu diễn đầu tiên nghệ sĩ 1 và 4 sẽ tham gia. Thì số lượng nghệ sĩ ở buổi biểu đầu tiên, người mà biểu diễn như các chú hề sẽ bằng 1. Và số lượng người biểu diễn ở buổi thứ 2, người mà biểu diễn như 1 acrobat cũng là 1.
Ở ví dụ thứ 2, không có cách nào để chia.
Ở ví dụ thứ 3, một trong những cách chia thỏa mãn: ở buổi biểu diễn thứ nhất nghệ sĩ thứ 3 và thứ 4 sẽ tham gia. Thì khi đó buổi biểu diễn đầu tiên có 2 nghệ sĩ người mà biểu diễn như một chú hề. Và số lượng nghệ sĩ ở buổi biểu diễn thứ 2 người mà biểu diễn như acrobats cũng là 2.
Hướng dẫn:
Chú ý rằng, chỉ có 4 loại nghệ sĩ: <<0;0>>,<<0;1>>,<<1;0>>,<<1;1>>
Vì vậy tất cả vấn đề được mô tả với 4 số nguyên - số họa sĩ của mỗi loại. Chúng ta nói rằngm có n(a) <<0;0>> nghệ sĩ, n(b) <<0;1>> nghệ sĩ, n(c) <<1;0>> nghệ sĩ, n(d) <<1;1>> nghệ sĩ.
Cùng cách đó, việc lựa chọn các nghệ sĩ cho buổi biểu diễn đầu tiên có thể được mô tả với 4 số nguyên 0<=a<=n(a),0<=b<=n(b),0<=c<=n(c),0<=d<=n(d).
Chú ý rằng, có một số hạn chế trên a,b,c,d
Cụ thể, chúng ta cần chọn chính xác một nữa nghệ sĩ: a+b+c+d=n/2;
Chúng ta cũng có một yêu cầu rằng số chú hề ở buổi biểu diễn đầu tiên c+d phải bằng số acrobats ở buổi biểu diễn thứ 2 (n(b)-b+n(d)-d):c+d=n(b)-b+n(d)-d, vì vậy chúng ta có: b+c+2d=n(b)+n(d).
Câu hỏi này là cần thiết và đủ. Vì vậy chúng ta có 4 biến và 2 phương trình. Chúng ta có thể chạy trâu với 2 biến bất kỳ, tính sử dụng 2 biến khác nhau. Và nếu mọi thứ đến tốt đẹp, in ra kết quả.
Độ phức tạp O(n^2).
Lời giải:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000;
int n;
char s[maxn + 10], t[maxn + 10];
vector<int> a, b, c, d;

int main() {
 scanf("%d", &n);
 scanf("%s%s", s + 1, t + 1);
 for (int i = 1; i <= n; ++i)
  if (s[i] == '0' && t[i] == '0') a.push_back(i);
  else if (s[i] == '1' && t[i] == '0') b.push_back(i);
  else if (s[i] == '0' && t[i] == '1') c.push_back(i);
  else if (s[i] == '1' && t[i] == '1') d.push_back(i);
 for (int i = 0; i <= (int)b.size(); ++i)
  for (int j = 0; j <= (int)d.size(); ++j) {
   int s = (int)c.size() - i - 2 * j + (int)d.size();
   if (s >= 0 && s <= (int)c.size()) {
    int all = i + s + j;
    int k = n / 2 - all;
    if (k >= 0 && k <= (int)a.size()) {
     for (int p = 0; p < k; ++p) printf("%d ", a[p]);
     for (int p = 0; p < i; ++p) printf("%d ", b[p]);
     for (int p = 0; p < s; ++p) printf("%d ", c[p]);
     for (int p = 0; p < j; ++p) printf("%d ", d[p]);
     return 0;
    }
   }
  }
 printf("-1"); 

}