Advertisement
islomiddin

#Code

Mar 1st, 2019
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 6.20 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         try {
  6.             InputStream inputStream = new FileInputStream("a_example.txt");
  7.             InputReader in = new InputReader(inputStream);
  8.             PrintWriter out = new PrintWriter(new File("a_out.txt"));
  9.             Solver solver = new Solver();
  10.             solver.solve(in, out);
  11.             inputStream.close();
  12.             out.close();
  13.         } catch (IOException e) {
  14.             throw new RuntimeException(e);
  15.         }
  16.     }
  17.     static class Solver {
  18.         public void solve(InputReader in, PrintWriter out) {
  19.             int N = in.nextInt();
  20.             Photo[] photos = new Photo[N];
  21.             int vert = 0, hor = 0;
  22.             for (int i = 0; i < N; ++i) {
  23.                 char or = in.next().charAt(0);
  24.                 vert += or == 'V' ? 1 : 0;
  25.                 hor += or == 'H' ? 1 : 0;
  26.                 int M = in.nextInt();
  27.                 photos[i] = new Photo(M, or);
  28.                 for (int j = 0; j < M; ++j) {
  29.                     String tag = in.next();
  30.                     photos[i].addTag(tag);
  31.                 }
  32.             }
  33.             int tot = hor + vert / 2;
  34.             int h_min = 101;
  35.             int v_min = 101;
  36.             int h_ind = 0;
  37.             int v_ind = 0;
  38.             for (int i = 0; i < N; ++i) {
  39.                 if (photos[i].or == 'H' && photos[i].M < h_min) {
  40.                     h_min = photos[i].M;
  41.                     h_ind = i;
  42.                 }
  43.                 if (photos[i].or == 'V' && photos[i].M < v_min) {
  44.                     v_min = photos[i].M;
  45.                     v_ind = i;
  46.                 }
  47.             }
  48.             int nextv_ind = 0;
  49.             int minv = 101;
  50.             for (int i = 0; i < N; ++i) {
  51.                 Set<String> tmp = new HashSet<>(photos[v_ind].tags);
  52.                 tmp.retainAll(photos[i].tags);
  53.                 if (i != v_ind && photos[i].or == 'V' && tmp.size() < minv) {
  54.                     minv = tmp.size();
  55.                     nextv_ind = i;
  56.                 }
  57.             }
  58.             //if (photos[h_ind].tags.size() <= minv) {
  59.             Slide[] slides = new Slide[tot];
  60.             slides[0] = new Slide(h_ind, -1, photos[h_ind].tags);
  61.             boolean[] taken = new boolean[N];
  62.             taken[h_ind] = true;
  63.             for (int i = 1; i < N; ++i) {
  64.                 int m = 0;
  65.                 int l = -1, r = -1;
  66.                 for (int j = 0; j < N; ++j) {
  67.                     if (!taken[j]) {
  68.                         HashSet<String> inter = new HashSet<>(slides[i - 1].tags);
  69.                         inter.retainAll(photos[j].tags);
  70.                         /*if (photos[j].or == 'V') {
  71.                             int next_min = 101;
  72.                             for (int k = 0; k < N; ++k) {
  73.                                 Set<String> tmp = new HashSet<>(photos[j].tags);
  74.                                 tmp.retainAll(photos[k].tags);
  75.                                 if (!taken[k] && tmp.size() < next_min) {
  76.                                     Set<String> un = new HashSet<>(photos[j].tags);
  77.                                     un.addAll(photos[k].tags);
  78.                                     inter.retainAll(un);
  79.                                     if (inter.size() > m) {
  80.                                         m = inter.size();
  81.                                         r = k;
  82.                                     }
  83.                                     next_min = tmp.size();
  84.                                 }
  85.                             }
  86.                             HashSet<String> un = new HashSet<>(photos[j].tags);
  87.                             un.addAll(photos[r].tags);
  88.                             slides[i] = new Slide(j, r, un);
  89.                             taken[j] = true;
  90.                             taken[r] = true;
  91.                         } else*/ if (inter.size() >= m) {
  92.                             m = inter.size();
  93.                             l = j;
  94.                         }
  95.                     }
  96.                 }
  97.                 if (l != -1) {
  98.                     taken[l] = true;
  99.                     slides[i] = new Slide(l, r, photos[l].tags);
  100.                 }
  101.             }
  102.             for (Slide s : slides) {
  103.                 if (s != null &&s.r == -1) {
  104.                     out.println(s.l);
  105.                 } else if (s != null) {
  106.                     out.println(s.l + " " + s.r);
  107.                 }
  108.             }
  109.         }
  110.     }
  111.     static class Photo {
  112.         int M;
  113.         char or;
  114.         HashSet<String> tags;
  115.         public Photo(int m, char o) {
  116.             M = m;
  117.             or = o;
  118.             tags = new HashSet<>();
  119.         }
  120.         public void addTag(String t) {
  121.             tags.add(t);
  122.         }
  123.     }
  124.     static class Slide {
  125.         int l, r;
  126.         HashSet<String> tags;
  127.         public Slide(int ll, int rr, HashSet<String> set) {
  128.             l = ll;
  129.             r = rr;
  130.             tags = new HashSet<>(set);
  131.         }
  132.     }
  133.     static class InputReader {
  134.         public BufferedReader reader;
  135.         public StringTokenizer tokenizer;
  136.         public InputReader(InputStream stream) {
  137.             reader = new BufferedReader(new InputStreamReader(stream), 32768);
  138.             tokenizer = null;
  139.         }
  140.         public String next() {
  141.             while (tokenizer == null || !tokenizer.hasMoreElements()) {
  142.                 try {
  143.                     tokenizer = new StringTokenizer(reader.readLine());
  144.                 } catch (IOException e) {
  145.                     throw new RuntimeException(e);
  146.                 }
  147.             }
  148.             return tokenizer.nextToken();
  149.         }
  150.         public String nextLine() {
  151.             String s = "";
  152.             try {
  153.                 s = reader.readLine();
  154.             } catch (IOException e) {
  155.                 throw new RuntimeException(e);
  156.             }
  157.             return s;
  158.         }
  159.         public int nextInt() {
  160.             return Integer.parseInt(next());
  161.         }
  162.         public long nextLong() {
  163.             return Long.parseLong(next());
  164.         }
  165.         public double nextDouble() {
  166.             return Double.parseDouble(next());
  167.         }
  168.     }
  169. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement