Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class Main {
- public static void main(String[] args) {
- try {
- InputStream inputStream = new FileInputStream("a_example.txt");
- InputReader in = new InputReader(inputStream);
- PrintWriter out = new PrintWriter(new File("a_out.txt"));
- Solver solver = new Solver();
- solver.solve(in, out);
- inputStream.close();
- out.close();
- } catch (IOException e) {
- throw new RuntimeException(e);
- }
- }
- static class Solver {
- public void solve(InputReader in, PrintWriter out) {
- int N = in.nextInt();
- Photo[] photos = new Photo[N];
- int vert = 0, hor = 0;
- for (int i = 0; i < N; ++i) {
- char or = in.next().charAt(0);
- vert += or == 'V' ? 1 : 0;
- hor += or == 'H' ? 1 : 0;
- int M = in.nextInt();
- photos[i] = new Photo(M, or);
- for (int j = 0; j < M; ++j) {
- String tag = in.next();
- photos[i].addTag(tag);
- }
- }
- int tot = hor + vert / 2;
- int h_min = 101;
- int v_min = 101;
- int h_ind = 0;
- int v_ind = 0;
- for (int i = 0; i < N; ++i) {
- if (photos[i].or == 'H' && photos[i].M < h_min) {
- h_min = photos[i].M;
- h_ind = i;
- }
- if (photos[i].or == 'V' && photos[i].M < v_min) {
- v_min = photos[i].M;
- v_ind = i;
- }
- }
- int nextv_ind = 0;
- int minv = 101;
- for (int i = 0; i < N; ++i) {
- Set<String> tmp = new HashSet<>(photos[v_ind].tags);
- tmp.retainAll(photos[i].tags);
- if (i != v_ind && photos[i].or == 'V' && tmp.size() < minv) {
- minv = tmp.size();
- nextv_ind = i;
- }
- }
- //if (photos[h_ind].tags.size() <= minv) {
- Slide[] slides = new Slide[tot];
- slides[0] = new Slide(h_ind, -1, photos[h_ind].tags);
- boolean[] taken = new boolean[N];
- taken[h_ind] = true;
- for (int i = 1; i < N; ++i) {
- int m = 0;
- int l = -1, r = -1;
- for (int j = 0; j < N; ++j) {
- if (!taken[j]) {
- HashSet<String> inter = new HashSet<>(slides[i - 1].tags);
- inter.retainAll(photos[j].tags);
- /*if (photos[j].or == 'V') {
- int next_min = 101;
- for (int k = 0; k < N; ++k) {
- Set<String> tmp = new HashSet<>(photos[j].tags);
- tmp.retainAll(photos[k].tags);
- if (!taken[k] && tmp.size() < next_min) {
- Set<String> un = new HashSet<>(photos[j].tags);
- un.addAll(photos[k].tags);
- inter.retainAll(un);
- if (inter.size() > m) {
- m = inter.size();
- r = k;
- }
- next_min = tmp.size();
- }
- }
- HashSet<String> un = new HashSet<>(photos[j].tags);
- un.addAll(photos[r].tags);
- slides[i] = new Slide(j, r, un);
- taken[j] = true;
- taken[r] = true;
- } else*/ if (inter.size() >= m) {
- m = inter.size();
- l = j;
- }
- }
- }
- if (l != -1) {
- taken[l] = true;
- slides[i] = new Slide(l, r, photos[l].tags);
- }
- }
- for (Slide s : slides) {
- if (s != null &&s.r == -1) {
- out.println(s.l);
- } else if (s != null) {
- out.println(s.l + " " + s.r);
- }
- }
- }
- }
- static class Photo {
- int M;
- char or;
- HashSet<String> tags;
- public Photo(int m, char o) {
- M = m;
- or = o;
- tags = new HashSet<>();
- }
- public void addTag(String t) {
- tags.add(t);
- }
- }
- static class Slide {
- int l, r;
- HashSet<String> tags;
- public Slide(int ll, int rr, HashSet<String> set) {
- l = ll;
- r = rr;
- tags = new HashSet<>(set);
- }
- }
- static class InputReader {
- public BufferedReader reader;
- public StringTokenizer tokenizer;
- public InputReader(InputStream stream) {
- reader = new BufferedReader(new InputStreamReader(stream), 32768);
- tokenizer = null;
- }
- public String next() {
- while (tokenizer == null || !tokenizer.hasMoreElements()) {
- try {
- tokenizer = new StringTokenizer(reader.readLine());
- } catch (IOException e) {
- throw new RuntimeException(e);
- }
- }
- return tokenizer.nextToken();
- }
- public String nextLine() {
- String s = "";
- try {
- s = reader.readLine();
- } catch (IOException e) {
- throw new RuntimeException(e);
- }
- return s;
- }
- public int nextInt() {
- return Integer.parseInt(next());
- }
- public long nextLong() {
- return Long.parseLong(next());
- }
- public double nextDouble() {
- return Double.parseDouble(next());
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement