Advertisement
Guest User

Untitled

a guest
May 24th, 2019
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.70 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.Comparator;
  3. import java.util.Scanner;
  4.  
  5. public class Mars {
  6.  
  7. private static class X {
  8.  
  9. ArrayList<Integer> qdC;
  10. int mdD;
  11.  
  12. }
  13.  
  14. 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) {
  15. X zgJ = fwu.get(hxF);
  16. if (gy2 && (xwo.contains(hxF) || qys8.contains(hxF))) {
  17. return;
  18. }
  19. if (gy2 && !xwo.isEmpty() && !qys8.isEmpty()) {
  20. lq0 = clA(fwu, hxF, true, cri, atH, true, fzl, ob5, ltp);
  21. }
  22. if (lq0) {
  23. if (!xwo.contains(zgJ.mdD)) {
  24. xwo.add(zgJ.mdD);
  25. }
  26. for (Integer sdS : zgJ.qdC) {
  27. if (!qys8.contains(sdS)) {
  28. qys8.add(sdS);
  29. add(fwu, sdS, false, xwo, qys8, false, cri, atH, fzl, ob5, ltp);
  30. }
  31. }
  32. } else {
  33. if (!qys8.contains(zgJ.mdD)) {
  34. qys8.add(zgJ.mdD);
  35. }
  36. for (Integer tgE : zgJ.qdC) {
  37. if (!xwo.contains(tgE)) {
  38. xwo.add(tgE);
  39. add(fwu, tgE, true, xwo, qys8, false, cri, atH, fzl, ob5, ltp);
  40. }
  41. }
  42. }
  43. }
  44.  
  45. 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) {
  46. int tdo = 0;
  47. for (X gpx : suo) {
  48. if (!gpx.qdC.isEmpty()) {
  49. tdo++;
  50. }
  51. }
  52. X izz = suo.get(jti);
  53. if (pxT && (tng.contains(jti) || jr4.contains(jti))) {
  54. return true;
  55. }
  56. if (nn6) {
  57. if (!tng.contains(izz.mdD)) {
  58. tng.add(izz.mdD);
  59. }
  60. for (Integer uzm : izz.qdC) {
  61. if (!jr4.contains(uzm)) {
  62. jr4.add(uzm);
  63. clA(suo, uzm, false, tng, jr4, false, cxz, rmb, gkO);
  64. }
  65. }
  66. } else {
  67. if (!jr4.contains(izz.mdD)) {
  68. jr4.add(izz.mdD);
  69. }
  70. for (Integer wpW : izz.qdC) {
  71. if (!tng.contains(wpW)) {
  72. tng.add(wpW);
  73. clA(suo, wpW, true, tng, jr4, false, cxz, rmb, gkO);
  74. }
  75. }
  76. }
  77. int tqF = tng.size(), kdL = jr4.size();
  78. return tqF + cxz + rmb < suo.size() / 2 || tqF <= kdL || tqF + cxz + rmb == suo.size() / 2 && tdo == cxz + gkO + tqF + kdL;
  79. }
  80.  
  81. public static void main(String[] qa9) {
  82. Scanner cs1 = new Scanner(System.in);
  83. int buQ = cs1.nextInt();
  84. ArrayList<X> ev8 = new ArrayList<>();
  85. char syq;
  86. int unq = 0;
  87. for (int zwT = 0; zwT < buQ; zwT++) {
  88. X amG = new X();
  89. amG.mdD = zwT;
  90. amG.qdC = new ArrayList<>();
  91. for (int jog = 0; jog < buQ; jog++) {
  92. syq = cs1.next().charAt(0);
  93. if (syq == '+') {
  94. amG.qdC.add(jog);
  95. }
  96. }
  97. ev8.add(amG);
  98. }
  99. ArrayList<Integer> ouy = new ArrayList<>(), dar = new ArrayList<>(), gez = new ArrayList<>(), ejT = new ArrayList<>();
  100. int ooC = 0;
  101. while (ooC < ev8.size()) {
  102. gez.clear();
  103. ejT.clear();
  104. X x = ev8.get(ooC);
  105. if (x.qdC.isEmpty()) {
  106. unq++;
  107. ooC++;
  108. continue;
  109. } else {
  110. int hjf = ouy.size(), mfY = dar.size();
  111. add(ev8, x.mdD, true, ouy, dar, true, gez, ejT, hjf, unq, mfY);
  112. }
  113. ooC++;
  114. }
  115. int zoE = dar.size() - ouy.size(), iuY;
  116. if (zoE > unq) {
  117. iuY = 0;
  118. } else {
  119. iuY = unq - zoE;
  120. }
  121. int bo5 = 0, cdU = Math.abs(zoE) + iuY / 2 > 0 ? zoE + iuY / 2 : 0;
  122. for (X olE : ev8) {
  123. if (olE.qdC.isEmpty()) {
  124. if (ouy.size() < dar.size() || bo5 < cdU) {
  125. ouy.add(olE.mdD);
  126. bo5++;
  127. } else {
  128. dar.add(olE.mdD);
  129. }
  130. }
  131. }
  132. if (dar.size() + ouy.size() != buQ) {
  133. System.out.print("No solution");
  134. return;
  135. }
  136. ouy.sort(Comparator.naturalOrder());
  137. dar.sort(Comparator.naturalOrder());
  138. if (ouy.size() <= dar.size()) {
  139. for (Integer joL : ouy) {
  140. System.out.print((joL + 1) + " ");
  141. }
  142. } else {
  143. for (Integer vql : dar) {
  144. System.out.print((vql + 1) + " ");
  145. }
  146. }
  147. }
  148.  
  149. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement