Guest User

Untitled

a guest
Dec 19th, 2016
705
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.49 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.io.PrintWriter;
  5. import java.util.Arrays;
  6. import java.util.StringTokenizer;
  7. import java.util.TreeSet;
  8.  
  9. public class AuctionNlogN {
  10.     private void solve() throws IOException {
  11.         int n = readInt();
  12.         int[] maxBet = new int[n];
  13.         Arrays.fill(maxBet, -1);
  14.         TreeSet<Integer>[] allBets = new TreeSet[n];
  15.         for (int man = 0; man < n; man++) {
  16.             allBets[man] = new TreeSet<>();
  17.         }
  18.         for (int i = 0; i < n; i++) {
  19.             int man = readInt() - 1;
  20.             int bet = readInt();
  21.             allBets[man].add(bet);
  22.             maxBet[man] = bet;
  23.         }
  24.         TreeSet<Integer> set = new TreeSet<>((a, b) -> {
  25.             int res = Integer.compare(maxBet[a], maxBet[b]);
  26.             if (res == 0) {
  27.                 res = Integer.compare(a, b);
  28.             }
  29.             return res;
  30.         });
  31.         for (int man = 0; man < n; man++) {
  32.             if (allBets[man].size() > 0) {
  33.                 set.add(man);
  34.             }
  35.         }
  36.         int q = readInt();
  37.         for (int i = 0; i < q; i++) {
  38.             int cnt = readInt();
  39.             int[] absent = new int[cnt];
  40.             for (int j = 0; j < cnt; j++) {
  41.                 absent[j] = readInt() - 1;
  42.             }
  43.             for (int man : absent) {
  44.                 set.remove(man);
  45.             }
  46.             if (set.isEmpty()) {
  47.                 out.println("0 0");
  48.             } else {
  49.                 int winner = set.pollLast();
  50.                 if (set.isEmpty()) {
  51.                     out.println((winner + 1) + " " + allBets[winner].first());
  52.                 } else {
  53.                     int loser = set.last();
  54.                     out.println((winner + 1) + " " + allBets[winner].higher(maxBet[loser]));
  55.                 }
  56.                 set.add(winner);
  57.             }
  58.             for (int man : absent) {
  59.                 if (allBets[man].size() > 0) {
  60.                     set.add(man);
  61.                 }
  62.             }
  63.         }
  64.     }
  65.  
  66. //------------------------------------------------------------------------------
  67.     public static void main(String[] args) {
  68.         new AuctionNlogN().run();
  69.     }
  70.  
  71.     private void run() {
  72.         try {
  73.             initIO();
  74.             solve();
  75.             in.close();
  76.             out.close();
  77.         } catch (Throwable e) {
  78.             throw new RuntimeException(e);
  79.         }
  80.     }
  81.  
  82.     private BufferedReader in;
  83.     private StringTokenizer tok;
  84.     private PrintWriter out;
  85.  
  86.     private void initIO() throws IOException {
  87.         in = new BufferedReader(new InputStreamReader(System.in));
  88.         out = new PrintWriter(System.out);
  89. //        in = new BufferedReader(new FileReader(new File("input.txt")));
  90. //        out = new PrintWriter(new File("output.txt"));
  91.     }
  92.  
  93.     private String readString() throws IOException {
  94.         while (tok == null || !tok.hasMoreTokens()) {
  95.             tok = new StringTokenizer(in.readLine());
  96.         }
  97.         return tok.nextToken();
  98.     }
  99.  
  100.     @SuppressWarnings("unused")
  101.     private int readInt() throws IOException {
  102.         return Integer.parseInt(readString());
  103.     }
  104.  
  105.     @SuppressWarnings("unused")
  106.     private long readLong() throws IOException {
  107.         return Integer.parseInt(readString());
  108.     }
  109.  
  110.     @SuppressWarnings("unused")
  111.     private double readDouble() throws IOException {
  112.         return Double.parseDouble(readString());
  113.     }
  114. }
Add Comment
Please, Sign In to add comment