Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.Comparator;
- import java.util.Scanner;
- public class Mars {
- private static class X {
- ArrayList<Integer> qdC;
- int mdD;
- }
- private static void add(ArrayList<X> fwu, int hxF, boolean lq0, ArrayList<Integer> xwo, ArrayList<Integer> qys8, boolean gy2, ArrayList<Integer> cri, ArrayList<Integer> atH, int fzl, int ob5, int ltp) {
- X zgJ = fwu.get(hxF);
- if (gy2 && (xwo.contains(hxF) || qys8.contains(hxF))) {
- return;
- }
- if (gy2 && !xwo.isEmpty() && !qys8.isEmpty()) {
- lq0 = clA(fwu, hxF, true, cri, atH, true, fzl, ob5, ltp);
- }
- if (lq0) {
- if (!xwo.contains(zgJ.mdD)) {
- xwo.add(zgJ.mdD);
- }
- for (Integer sdS : zgJ.qdC) {
- if (!qys8.contains(sdS)) {
- qys8.add(sdS);
- add(fwu, sdS, false, xwo, qys8, false, cri, atH, fzl, ob5, ltp);
- }
- }
- } else {
- if (!qys8.contains(zgJ.mdD)) {
- qys8.add(zgJ.mdD);
- }
- for (Integer tgE : zgJ.qdC) {
- if (!xwo.contains(tgE)) {
- xwo.add(tgE);
- add(fwu, tgE, true, xwo, qys8, false, cri, atH, fzl, ob5, ltp);
- }
- }
- }
- }
- private static boolean clA(ArrayList<X> suo, int jti, boolean nn6, ArrayList<Integer> tng, ArrayList<Integer> jr4, boolean pxT, int cxz, int rmb, int gkO) {
- int tdo = 0;
- for (X gpx : suo) {
- if (!gpx.qdC.isEmpty()) {
- tdo++;
- }
- }
- X izz = suo.get(jti);
- if (pxT && (tng.contains(jti) || jr4.contains(jti))) {
- return true;
- }
- if (nn6) {
- if (!tng.contains(izz.mdD)) {
- tng.add(izz.mdD);
- }
- for (Integer uzm : izz.qdC) {
- if (!jr4.contains(uzm)) {
- jr4.add(uzm);
- clA(suo, uzm, false, tng, jr4, false, cxz, rmb, gkO);
- }
- }
- } else {
- if (!jr4.contains(izz.mdD)) {
- jr4.add(izz.mdD);
- }
- for (Integer wpW : izz.qdC) {
- if (!tng.contains(wpW)) {
- tng.add(wpW);
- clA(suo, wpW, true, tng, jr4, false, cxz, rmb, gkO);
- }
- }
- }
- int tqF = tng.size(), kdL = jr4.size();
- return tqF + cxz + rmb < suo.size() / 2 || tqF <= kdL || tqF + cxz + rmb == suo.size() / 2 && tdo == cxz + gkO + tqF + kdL;
- }
- public static void main(String[] qa9) {
- Scanner cs1 = new Scanner(System.in);
- int buQ = cs1.nextInt();
- ArrayList<X> ev8 = new ArrayList<>();
- char syq;
- int unq = 0;
- for (int zwT = 0; zwT < buQ; zwT++) {
- X amG = new X();
- amG.mdD = zwT;
- amG.qdC = new ArrayList<>();
- for (int jog = 0; jog < buQ; jog++) {
- syq = cs1.next().charAt(0);
- if (syq == '+') {
- amG.qdC.add(jog);
- }
- }
- ev8.add(amG);
- }
- ArrayList<Integer> ouy = new ArrayList<>(), dar = new ArrayList<>(), gez = new ArrayList<>(), ejT = new ArrayList<>();
- int ooC = 0;
- while (ooC < ev8.size()) {
- gez.clear();
- ejT.clear();
- X x = ev8.get(ooC);
- if (x.qdC.isEmpty()) {
- unq++;
- ooC++;
- continue;
- } else {
- int hjf = ouy.size(), mfY = dar.size();
- add(ev8, x.mdD, true, ouy, dar, true, gez, ejT, hjf, unq, mfY);
- }
- ooC++;
- }
- int zoE = dar.size() - ouy.size(), iuY;
- if (zoE > unq) {
- iuY = 0;
- } else {
- iuY = unq - zoE;
- }
- int bo5 = 0, cdU = Math.abs(zoE) + iuY / 2 > 0 ? zoE + iuY / 2 : 0;
- for (X olE : ev8) {
- if (olE.qdC.isEmpty()) {
- if (ouy.size() < dar.size() || bo5 < cdU) {
- ouy.add(olE.mdD);
- bo5++;
- } else {
- dar.add(olE.mdD);
- }
- }
- }
- if (dar.size() + ouy.size() != buQ) {
- System.out.print("No solution");
- return;
- }
- ouy.sort(Comparator.naturalOrder());
- dar.sort(Comparator.naturalOrder());
- if (ouy.size() <= dar.size()) {
- for (Integer joL : ouy) {
- System.out.print((joL + 1) + " ");
- }
- } else {
- for (Integer vql : dar) {
- System.out.print((vql + 1) + " ");
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement