NEERC/database/database_petr.java

   1 import java.io.BufferedReader;
   2 import java.io.FileReader;
   3 import java.io.PrintWriter;
   4 import java.io.IOException;
   5 import java.util.StringTokenizer;
   6 import java.util.Set;
   7 import java.util.Map;
   8 import java.util.HashMap;
   9
  10 public class database_petr implements Runnable {
  11     private void solve() throws IOException {
  12         int n = nextInt();
  13         int m = nextInt();
  14         Map<Long, Integer>[][] sets = new Map[m][m];
  15         for (int i = 0; i < m; ++i)
  16             for (int j = i + 1; j < m; ++j)
  17                 sets[i][j] = new HashMap<Long, Integer>();
  18         for (int l = 0; l < n; ++l) {
  19             String s = reader.readLine();
  20             String[] p = s.split(",");
  21             long[] h = new long[p.length];
  22             for (int i = 0; i < p.length; ++i)
  23                 h[i] = getHash(p[i]);
  24             if (p.length != m)
  25                 throw new RuntimeException();
  26             for (int i = 0; i < m; ++i)
  27                 for (int j = i + 1; j < m; ++j) {
  28                     long st = h[i] * 597431956418123L + h[j];
  29                     if (sets[i][j].containsKey(st)) {
  30                         writer.println("NO");
  31                         writer.println((sets[i][j].get(st) + 1) + " " + (l + 1));
  32                         writer.println((i + 1) + " " + (j + 1));
  33                         return;
  34                     }
  35                     sets[i][j].put(st, l);
  36                 }
  37         }
  38         writer.println("YES");
  39     }
  40
  41     private long getHash(String s) {
  42         long res = 1;
  43         for (int i = 0; i < s.length(); ++i)
  44             res = res * 3137 + s.charAt(i);
  45         return res;
  46     }
  47
  48
  49     public static void main(String[] args) throws InterruptedException {
  50         Thread thread = new Thread(new database_petr());
  51         thread.start();
  52         thread.join();
  53     }
  54
  55     static final String TASK_ID = "database";
  56     static final String IN_FILE = TASK_ID + ".in";
  57     static final String OUT_FILE = TASK_ID + ".out";
  58     BufferedReader reader;
  59     StringTokenizer tokenizer;
  60     PrintWriter writer;
  61
  62     public void run() {
  63         try {
  64             reader = new BufferedReader(new FileReader(IN_FILE));
  65             tokenizer = null;
  66             writer = new PrintWriter(OUT_FILE);
  67             solve();
  68             reader.close();
  69             writer.close();
  70         } catch (Exception e) {
  71             e.printStackTrace();
  72             System.exit(1);
  73         }
  74     }
  75
  76     int nextInt() throws IOException {
  77         return Integer.parseInt(nextToken());
  78     }
  79
  80     long nextLong() throws IOException {
  81         return Long.parseLong(nextToken());
  82     }
  83
  84     double nextDouble() throws IOException {
  85         return Double.parseDouble(nextToken());
  86     }
  87
  88     String nextToken() throws IOException {
  89         while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  90             tokenizer = new StringTokenizer(reader.readLine());
  91         }
  92         return tokenizer.nextToken();
  93     }
  94 }