NEERC/database/database_rs.java

   1 import java.io.*;
   2 import java.util.*;
   3
   4 public class database_rs implements Runnable {
   5     private BufferedReader in;
   6     private PrintWriter out;
   7
   8     private void check(boolean expr, String msg) {
   9         if (!expr) {
  10             throw new Error(msg);
  11         }
  12     }
  13
  14     private void checkBounds(int n, int low, int hi, String nStr) {
  15         check((low <= n) && (n <= hi), nStr + " is not in [" + low + ", " + hi + "]");
  16     }
  17
  18     private class Row implements Comparable<Row> {
  19         public int u, v;
  20         public int num;
  21
  22         public int compareTo(Row that) {
  23             if (u != that.u) {
  24                 return u - that.u;
  25             }
  26             if (v != that.v) {
  27                 return v - that.v;
  28             }
  29             return num - that.num;
  30         }
  31
  32         @Override
  33         public boolean equals(Object o) {
  34             Row that = (Row) o;
  35             return (u == that.u) && (v == that.v) && (num == that.num);
  36         }
  37     }
  38
  39     private void solve() throws IOException {
  40         StringTokenizer st = new StringTokenizer(in.readLine());
  41         int n = Integer.parseInt(st.nextToken());
  42         int m = Integer.parseInt(st.nextToken());
  43         checkBounds(n, 1, 10000, "n");
  44         checkBounds(m, 1, 10, "m");
  45         int[][] t = new int[n][m];
  46         Map<String, Integer> words = new HashMap<String, Integer>();
  47         int wordsCount = 0;
  48         for (int i = 0; i < n; i++) {
  49             String line = in.readLine();
  50             check(line.length() <= 80, "line too long");
  51             st = new StringTokenizer(line, ",");
  52             for (int j = 0; j < m; j++) {
  53                 String word = st.nextToken();
  54                 for (int u = 0; u < word.length(); u++) {
  55                     char ch = word.charAt(u);
  56                     check((' ' <= ch) && (ch <= '~'), "invalid symbol in word: " + ch);
  57                 }
  58                 check(word.charAt(0) != ' ', "leading spaces in word");
  59                 check(word.charAt(word.length() - 1) != ' ', "trailing spaces in word");
  60                 if (!words.containsKey(word)) {
  61                     words.put(word, wordsCount++);
  62                 }
  63                 t[i][j] = words.get(word);
  64             }
  65         }
  66         Row[] rows = new Row[n];
  67         for (int i = 0; i < n; i++) {
  68             rows[i] = new Row();
  69         }
  70         for (int u = 0; u < m; u++) {
  71             for (int v = u + 1; v < m; v++) {
  72                 for (int i = 0; i < n; i++) {
  73                     rows[i].u = t[i][u];
  74                     rows[i].v = t[i][v];
  75                     rows[i].num = i + 1;
  76                 }
  77                 Arrays.sort(rows);
  78                 for (int i = 0; i < n - 1; i++) {
  79                     if (rows[i].u == rows[i + 1].u && rows[i].v == rows[i + 1].v) {
  80                         out.println("NO");
  81                         out.println(rows[i].num + " " + rows[i + 1].num);
  82                         out.println((u + 1) + " " + (v + 1));
  83                         return;
  84                     }
  85                 }
  86             }
  87         }
  88         out.println("YES");
  89     }
  90
  91     public static void main(String[] args) {
  92         new Thread(new database_rs()).start();
  93     }
  94
  95     public void run() {
  96         String problem = getClass().getName().split("_")[0];
  97         try {
  98             in = new BufferedReader(new FileReader(new File(problem + ".in")));
  99             out = new PrintWriter(new File(problem + ".out"));
 100             solve();
 101             in.close();
 102             out.close();
 103         } catch (IOException e) {
 104             e.printStackTrace();
 105             System.exit(1);
 106         }
 107     }
 108 }