fork download
copy 
  1.  
  2. import java.io.BufferedReader;
  3. import java.io.IOException;
  4. import java.io.InputStreamReader;
  5. import java.io.StreamTokenizer;
  6. import java.util.ArrayList;
  7. import java.util.Arrays;
  8. import java.util.EnumSet;
  9. import javax.print.attribute.standard.Sides;
  10.  
  11. public class strings_kp2 {
  12.  
  13.     static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
  14.     static int[] tableLong;
  15.     static int[] tableShort1;
  16.     static int[] tableShort2;
  17.  
  18.     static int[] createTable(int[] w) {
  19.         int[] table = new int[w.length];
  20.         int pos = 2;
  21.         int cnd = 0;
  22.  
  23.         table[0] = -1;
  24.         while (pos < w.length) {
  25.             if (w[pos - 1] == w[cnd]) {
  26.                 cnd++;
  27.                 table[pos] = cnd;
  28.                 pos++;
  29.  
  30.             } else if (cnd > 0) {
  31.                 cnd = table[cnd];
  32.             } else {
  33.                 table[pos] = 0;
  34.                 pos++;
  35.             }
  36.         }
  37.         return table;
  38.     }
  39.  
  40.     private static int kmp(int[] w, int[] s, int[] table) {
  41.  
  42.         int m = 0;
  43.         int i = 0;
  44.  
  45.         while (m + i < s.length) {
  46.             if (w[i] == s[m + i]) {
  47.                 if (i == w.length - 1) {
  48.                     return m;
  49.                 }
  50.                 i++;
  51.             } else {
  52.                 m = m + i - table[i];
  53.                 if (table[i] > -1) {
  54.                     i = table[i];
  55.                 } else {
  56.                     i = 0;
  57.                 }
  58.             }
  59.  
  60.         }
  61.         return s.length;
  62.     }
  63.  
  64.     static enum Side {
  65.  
  66.         T {
  67.  
  68.             Side opposite() {
  69.                 return Side.B;
  70.             }
  71.  
  72.             Side flip() {
  73.                 return Side.L;
  74.             }
  75.         }, L {
  76.  
  77.             Side opposite() {
  78.                 return Side.R;
  79.             }
  80.  
  81.             Side flip() {
  82.                 return Side.T;
  83.             }
  84.         }, R {
  85.  
  86.             Side opposite() {
  87.                 return Side.L;
  88.             }
  89.  
  90.             Side flip() {
  91.                 return Side.B;
  92.             }
  93.         }, B {
  94.  
  95.             Side opposite() {
  96.                 return Side.T;
  97.             }
  98.  
  99.             Side flip() {
  100.                 return Side.R;
  101.             }
  102.         };
  103.         Line[] lines;
  104.  
  105.         abstract Side opposite();
  106.  
  107.         abstract Side flip();
  108.     }
  109.  
  110.     static int nextInt() {
  111.         try {
  112.             st.nextToken();
  113.             return (int) st.nval;
  114.         } catch (IOException ex) {
  115.             return 0;
  116.         }
  117.     }
  118.  
  119.     static Side nextSide() {
  120.         try {
  121.             st.nextToken();
  122.             switch (st.sval.charAt(0)) {
  123.                 case 'T':
  124.                     return Side.T;
  125.                 case 'L':
  126.                     return Side.L;
  127.                 case 'R':
  128.                     return Side.R;
  129.                 default:
  130.                     return Side.B;
  131.             }
  132.         } catch (IOException ex) {
  133.             return Side.T;
  134.         }
  135.     }
  136.  
  137.     static enum Type {
  138.  
  139.         TL, TR, TB, LR, LB, RB;
  140.         int count;
  141.     }
  142.  
  143.     static int getType(int start, int end) {
  144.         switch (start) {
  145.             case 0:
  146.                 switch (end) {
  147.                     case 1:
  148.                         return 0;
  149.                     case 2:
  150.                         return 1;
  151.                     default:
  152.                         return 2;
  153.                 }
  154.             case 1:
  155.                 switch (end) {
  156.                     case 2:
  157.                         return 3;
  158.                     default:
  159.                         return 4;
  160.                 }
  161.             default:
  162.                 return 5;
  163.         }
  164.     }
  165.  
  166.     static final class Line {
  167.  
  168.         Side s1, s2;
  169.         int a, b;
  170.         Type type;
  171.         boolean used;
  172.  
  173.         private Line(Side s1, Side s2, int a, int b) {
  174.             if (s1.ordinal() > s2.ordinal()) {
  175.                 Side t = s1;
  176.                 s1 = s2;
  177.                 s2 = t;
  178.                 int ti = a;
  179.                 a = b;
  180.                 b = ti;
  181.             }
  182.             this.s1 = s1;
  183.             this.s2 = s2;
  184.             this.a = a;
  185.             this.b = b;
  186.             s1.lines[a] = this;
  187.             s2.lines[b] = this;
  188.             setType();
  189.         }
  190.  
  191.         public String toString() {
  192.             return "(" + s1 + ":" + a + "," + s2 + ":" + b + ")";
  193.         }
  194.  
  195.         void setType() {
  196.             switch (s1) {
  197.                 case T:
  198.                     switch (s2) {
  199.                         case R:
  200.                             type = Type.TR;
  201.                             break;
  202.                         case L:
  203.                             type = Type.TL;
  204.                             break;
  205.                         default:
  206.                             type = Type.TB;
  207.                     }
  208.                     break;
  209.                 case L:
  210.                     switch (s2) {
  211.                         case R:
  212.                             type = Type.LR;
  213.                             break;
  214.                         default:
  215.                             type = Type.LB;
  216.                     }
  217.                     break;
  218.                 default:
  219.                     type = Type.RB;
  220.             }
  221.         }
  222.     }
  223.     static int n, m;
  224.     static boolean flip;
  225.     static int shortCount;
  226.     static ArrayList<Integer> theCycle = new ArrayList<Integer>();
  227.     static ArrayList<ArrayList<Integer>> allCycles = new ArrayList<ArrayList<Integer>>();
  228.     static ArrayList<Integer> cyclePoints = new ArrayList<Integer>();
  229.     static ArrayList<ArrayList<Integer>> allPoints = new ArrayList<ArrayList<Integer>>();
  230.     static ArrayList<Integer> cycleSides = new ArrayList<Integer>();
  231.     static ArrayList<Integer> rotations = new ArrayList<Integer>();
  232.  
  233.     static boolean findSolution() {
  234.         if (Type.LR.count > 0) {
  235.             return false;
  236.         }
  237.         if (Type.TR.count != Type.LB.count) {
  238.             return false;
  239.         }
  240.         if (Type.TL.count != Type.RB.count) {
  241.             return false;
  242.         }
  243.         if (Type.TB.count != m - (Type.TL.count + Type.TR.count)) {
  244.             return false;
  245.         }
  246.         shortCount = Math.min(Type.TL.count, Type.TR.count);
  247.  
  248.         int topSize = m - (shortCount * 2);
  249.         int sideSize = n - (shortCount * 2);
  250.  
  251.         if (Type.TL.count == Type.TR.count) {
  252.             theCycle.add(Type.TB.ordinal());
  253.             cyclePoints.add(shortCount);
  254.             cycleSides.add(0);
  255.             allCycles.add(theCycle);
  256.             allPoints.add(cyclePoints);
  257.             for (int i = shortCount + 1; i < shortCount + topSize; i++) {
  258.                 ArrayList<Integer> newCycle = new ArrayList<Integer>();
  259.                 ArrayList<Integer> newPoints = new ArrayList<Integer>();
  260.                 newCycle.add(Type.TB.ordinal());
  261.                 newPoints.add(i);
  262.                 allCycles.add(newCycle);
  263.                 allPoints.add(newPoints);
  264.             }
  265.             return true;
  266.         }
  267.         boolean right = Type.TL.count < Type.TR.count;
  268.  
  269.         int l = Side.L.ordinal();
  270.         int r = Side.R.ordinal();
  271.         int t = Side.T.ordinal();
  272.         int b = Side.B.ordinal();
  273.         int[][] nextSides = new int[4][m];
  274.         int[][] nextPoints = new int[4][m];
  275.         if (right) {
  276.             for (int i = 0; i < sideSize; i++) {
  277.                 nextSides[l][shortCount + i] = b;
  278.                 nextPoints[l][shortCount + i] = shortCount + sideSize - i - 1;
  279.                 nextSides[b][shortCount + sideSize - i - 1] = l;
  280.                 nextPoints[b][shortCount + sideSize - i - 1] = shortCount + i;
  281.  
  282.                 nextSides[r][shortCount + i] = t;
  283.                 nextPoints[r][shortCount + i] = m - shortCount - i - 1;
  284.                 nextSides[t][m - shortCount - i - 1] = r;
  285.                 nextPoints[t][m - shortCount - i - 1] = shortCount + i;
  286.             }
  287.  
  288.             for (int i = 0; i < topSize - sideSize; i++) {
  289.                 nextSides[t][shortCount + i] = b;
  290.                 nextPoints[t][shortCount + i] = shortCount + sideSize + i;
  291.                 nextSides[b][shortCount + sideSize + i] = t;
  292.                 nextPoints[b][shortCount + sideSize + i] = shortCount + i;
  293.             }
  294.         } else {
  295.             for (int i = 0; i < sideSize; i++) {
  296.                 nextSides[l][shortCount + i] = t;
  297.                 nextPoints[l][shortCount + i] = shortCount + i;
  298.                 nextSides[t][shortCount + i] = l;
  299.                 nextPoints[t][shortCount + i] = shortCount + i;
  300.  
  301.                 nextSides[r][shortCount + i] = b;
  302.                 nextPoints[r][shortCount + i] = m - shortCount - sideSize + i;
  303.                 nextSides[b][m - shortCount - sideSize + i] = r;
  304.                 nextPoints[b][m - shortCount - sideSize + i] = shortCount + i;
  305.             }
  306.  
  307.             for (int i = 0; i < topSize - sideSize; i++) {
  308.                 nextSides[b][shortCount + i] = t;
  309.                 nextPoints[b][shortCount + i] = shortCount + sideSize + i;
  310.                 nextSides[t][shortCount + sideSize + i] = b;
  311.                 nextPoints[t][shortCount + sideSize + i] = shortCount + i;
  312.             }
  313.         }
  314.         boolean[][] used = new boolean[4][m];
  315.         int curSide = t;
  316.         int curPos = shortCount;
  317.         while (!used[curSide][curPos]) {
  318.             used[curSide][curPos] = true;
  319.             int nextSide = nextSides[curSide][curPos];
  320.             int nextPos = nextPoints[curSide][curPos];
  321.             theCycle.add(getType(curSide, nextSide));
  322.             cyclePoints.add(curPos);
  323.             cycleSides.add(curSide % 3 == 0 ? 0 : 1);
  324.             curSide = 3 - nextSide;
  325.             curPos = nextPos;
  326.         }
  327.         allCycles.add(theCycle);
  328.         allPoints.add(cyclePoints);
  329.         for (int i = shortCount; i < shortCount + topSize; i++) {
  330.             if (!used[0][i]) {
  331.                 ArrayList<Integer> newCycle = new ArrayList<Integer>();
  332.                 ArrayList<Integer> newPoints = new ArrayList<Integer>();
  333.                 curSide = t;
  334.                 curPos = i;
  335.                 while (!used[curSide][curPos]) {
  336.                     used[curSide][curPos] = true;
  337.                     int nextSide = nextSides[curSide][curPos];
  338.                     int nextPos = nextPoints[curSide][curPos];
  339.                     newCycle.add(getType(curSide, nextSide));
  340.                     newPoints.add(curPos);
  341.                     curSide = 3 - nextSide;
  342.                     curPos = nextPos;
  343.                 }
  344.                 allCycles.add(newCycle);
  345.                 allPoints.add(newPoints);
  346.             }
  347.         }
  348.  
  349.  
  350.         return true;
  351.     }
  352.  
  353.     public static void main(String[] args) {
  354.         n = nextInt();
  355.         m = nextInt();
  356.  
  357.         if (n > m) {
  358.             flip = true;
  359.             int t = n;
  360.             n = m;
  361.             m = t;
  362.         }
  363.  
  364.         Side.T.lines = new Line[m];
  365.         Side.B.lines = new Line[m];
  366.         Side.L.lines = new Line[n];
  367.         Side.R.lines = new Line[n];
  368.  
  369.  
  370.         ArrayList<Line> lines = new ArrayList<Line>();
  371.  
  372.         for (int i = 0; i < n + m; i++) {
  373.             Side s1 = nextSide();
  374.             Side s2 = nextSide();
  375.             if (flip) {
  376.                 s1 = s1.flip();
  377.                 s2 = s2.flip();
  378.             }
  379.             lines.add(new Line(s1, s2, nextInt() - 1, nextInt() - 1));
  380.         }
  381.         for (Line l : lines) {
  382.             l.type.count++;
  383.         }
  384.  
  385.         if (!findSolution()) {
  386.             System.out.println("No solution");
  387.             return;
  388.         }
  389.         int[] longCycle = new int[theCycle.size()];
  390.         for (int i = 0; i < theCycle.size(); i++) {
  391.             longCycle[i] = theCycle.get(i);
  392.         }
  393.  
  394.  
  395.         int[] shortCycle1 = {0, 4, 5, 1};
  396.         int[] shortCycle2 = {0, 1, 5, 4};
  397.  
  398.         tableLong = createTable(longCycle);
  399.         tableShort1 = createTable(shortCycle1);
  400.         tableShort2 = createTable(shortCycle2);
  401.         rotations.add(0);
  402.         for (int i = 1; i < allCycles.size(); i++) {
  403.             int length = theCycle.size();
  404.             int[] curCycle = new int[length * 2];
  405.             for (int j = 0; j < length; j++) {
  406.                 curCycle[j] = allCycles.get(i).get(j);
  407.             }
  408.             for (int j = 0; j < length; j++) {
  409.                 curCycle[j + length] = allCycles.get(i).get(j);
  410.             }
  411.             rotations.add(kmp(longCycle, curCycle, tableLong));
  412.         }
  413.  
  414.         ArrayList<ArrayList<Line>> cycles = new ArrayList<ArrayList<Line>>();
  415.  
  416.         for (Line l : lines) {
  417.             if (!l.used) {
  418.                 ArrayList<Line> cycle = new ArrayList<Line>();
  419.                 Line next = l;
  420.                 while (!next.used) {
  421.                     cycle.add(next);
  422.                     next.used = true;
  423.                     if (!next.s2.opposite().lines[next.b].used) {
  424.                         next = next.s2.opposite().lines[next.b];
  425.                     } else if (!next.s1.opposite().lines[next.a].used) {
  426.                         next = next.s1.opposite().lines[next.a];
  427.                     }
  428.                 }
  429.                 cycles.add(cycle);
  430.             }
  431.         }
  432.  
  433.         int actualShortCount = 0;
  434.         int longCount = 0;
  435.  
  436.         int[] rows = new int[n];
  437.         int[] cols = new int[m];
  438.  
  439.         for (ArrayList<Line> cycle : cycles) {
  440.             int length = cycle.size();
  441.  
  442.  
  443.             int[] curCycle = new int[length * 2];
  444.             for (int i = 0; i < length; i++) {
  445.                 curCycle[i] = cycle.get(i).type.ordinal();
  446.             }
  447.             for (int i = 0; i < length; i++) {
  448.                 curCycle[length + i] = cycle.get(i).type.ordinal();
  449.             }
  450.  
  451.             if (length == 4) {
  452.                 int rot1 = kmp(shortCycle1, curCycle, tableShort1);
  453.                 int rot2 = kmp(shortCycle2, curCycle, tableShort2);
  454.                 if (rot1 != 8 || rot2 != 8) {
  455.                     for (Line l : cycle) {
  456.                         if (l.type == Type.TL) {
  457.                             rows[actualShortCount] = l.b;
  458.                             cols[actualShortCount] = l.a;
  459.                         } else if (l.type == Type.RB) {
  460.                             rows[n - 1 - actualShortCount] = l.a;
  461.                             cols[m - 1 - actualShortCount] = l.b;
  462.                         }
  463.                     }
  464.                     actualShortCount++;
  465.                     continue;
  466.                 }
  467.             }
  468.             if (length != longCycle.length) {
  469.                 System.out.println("No solution");
  470.                 return;
  471.             }
  472.  
  473.             int rot = kmp(longCycle, curCycle, tableLong);
  474.             if (rot == 2 * length) {
  475.                 System.out.println("No solution");
  476.                 return;
  477.             }
  478.             for (int i = 0; i < length; i++) {
  479.                 int pos = allPoints.get(longCount).get((i + rotations.get(longCount)) % length);
  480.                 int value = cycle.get((rot + i) % length).a;
  481.                 if (cycleSides.get(i) == 0) {
  482.                     cols[pos] = value;
  483.                 } else {
  484.                     rows[pos] = value;
  485.                 }
  486.             }
  487.             longCount++;
  488.  
  489.         }
  490.  
  491.         if (flip) {
  492.             int[] t = rows;
  493.             rows = cols;
  494.             cols = t;
  495.         }
  496.  
  497.         for (int i = 0; i < rows.length; i++) {
  498.             System.out.print((rows[i] + 1) + " ");
  499.         }
  500.         System.out.println();
  501.         for (int i = 0; i < cols.length; i++) {
  502.             System.out.print((cols[i] + 1) + " ");
  503.         }
  504.         System.out.println();
  505.     }
  506. }
  507.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QYJR6c
language:
Java (HotSpot 12)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!