fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class D implements Runnable {
  5.   static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  6.   static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
  7.   static StringTokenizer st = new StringTokenizer("");
  8.  
  9.   public static String next() {
  10.     try {
  11.     while (!st.hasMoreTokens()) {
  12.       String s = br.readLine();
  13.       if (s == null)
  14.         return null;
  15.       st = new StringTokenizer(s);
  16.     }
  17.     return st.nextToken();
  18.     } catch(Exception e)  {
  19.       return  null;
  20.     }
  21.   }
  22.  
  23.   public static void main(String[] asda) throws Exception {
  24.     new Thread(null, new D(), "D", 1<<26).start();
  25.   }
  26.  
  27.   public void run() {
  28.     // size of tournament, wins
  29.     int[][] winsToRank = new int[20][8];
  30.     winsToRank[1][0] = 1;
  31.  
  32.     winsToRank[2][0] = 2;
  33.     winsToRank[2][1] = 1;
  34.  
  35.     winsToRank[4][0] = 3;
  36.     winsToRank[4][1] = 2;
  37.     winsToRank[4][2] = 1;
  38.  
  39.     winsToRank[8][0] = 5;
  40.     winsToRank[8][1] = 3;
  41.     winsToRank[8][2] = 2;
  42.     winsToRank[8][3] = 1;
  43.  
  44.     winsToRank[16][0] = 9;
  45.     winsToRank[16][1] = 5;
  46.     winsToRank[16][2] = 3;
  47.     winsToRank[16][3] = 2;
  48.     winsToRank[16][4] = 1;
  49.  
  50.   //  generate();
  51.     int CASES = Integer.parseInt( next() );
  52.     int ccc = 1;
  53.     while (CASES-- > 0) {
  54.       out.println("Case #" + ccc++ + ":");
  55.  
  56.       N = Integer.parseInt( next() );
  57.       beats = new boolean[N][N];
  58.       for (int a = 0; a < N; a++) for (int b = 0; b < N; b++)
  59.         beats[a][b] = next().equals("1");
  60.  
  61.       if (N == 1) {
  62.         out.println("1 1");
  63.         continue;
  64.       }
  65.       if (N == 2) {
  66.         if (beats[0][1]) {
  67.           out.println("1 1");
  68.           out.println("2 2");
  69.         } else  {
  70.           out.println("2 2");
  71.           out.println("1 1");
  72.         }
  73.         continue;
  74.       }
  75.  
  76.       // max number of wins a player can have in a tournament
  77.       int[] maxWins = new int[N];
  78.       // canWin(p, players) = can p win the tournament if players are playing? players is len = 2,4,8,16
  79.       Set<Integer>[][] canWin = new TreeSet[N][N+1];
  80.       for (int p = 0; p < N; p++) for (int q = 0; q <= N; q++)
  81.         canWin[p][q] = new TreeSet<>();
  82.  
  83.       for (int p = 0; p < N; p++) {
  84.         Set<Integer> result = canWin[p][2];
  85.         for (int q = 0; q < N; q++) if (q != p && beats[p][q]) {
  86.           maxWins[p] = 1;
  87.           result.add( (1<<p)|(1<<q) );
  88.         }
  89.       }
  90.       for (int players = 4, wins = 2; players <= N; players *= 2, wins++) {
  91.         loop: for (int p = 0; p < N; p++) if (!canWin[p][players/2].isEmpty()) {
  92.           Set<Integer> result = canWin[p][players];
  93.  
  94.           for (int q = 0; q < N; q++) if (q != p && beats[p][q] && !canWin[q][players/2].isEmpty()) {
  95.             for (int qMatch : canWin[q][players/2]) for (int pMatch : canWin[p][players/2]) if ( (qMatch&pMatch) == 0 ) {
  96.               result.add( qMatch|pMatch );
  97.               if (players == N) {
  98.                 maxWins[p] = wins;
  99.                 continue loop;
  100.               }
  101.             }
  102.           }
  103.  
  104.           if (!result.isEmpty()) {
  105.             maxWins[p] = wins;
  106.           }
  107.         }
  108.       }
  109.  
  110.       int[] minRank = new int[N];
  111.       for (int p = 0; p < N; p++) {
  112.         int wins = 0;
  113.         for (int q = 0; q < N; q++) if (q != p && beats[p][q]) {
  114.           wins++;
  115.         }
  116.  
  117.         if (wins == N-1) {
  118.           minRank[p] = 1;
  119.           continue;
  120.         }
  121.  
  122.         if (N == 4) {
  123.           minRank[p] = 3;
  124.         } else if (N==8)  {
  125.           minRank[p] = 5;
  126.         } else {
  127.           minRank[p] = 9;
  128.         }
  129.       }
  130.       for (int p = 0; p < N; p++) {
  131.         int wins = maxWins[p];
  132.         out.println( winsToRank[N][wins] + " " + minRank[p] );
  133.       }
  134.     }
  135.     //
  136.     out.flush();
  137.     System.exit(0);
  138.   }
  139.   void generate() {
  140.     Random r = new Random();
  141.     int N = 16;
  142.     out.println(N);
  143.     int[][] val = new int[N][N];
  144.     for (int p = 0; p < N; p++) for (int q = p+1; q < N; q++) {
  145.       if (r.nextBoolean()) {
  146.         val[p][q] = 1;
  147.       } else  {
  148.         val[q][p] = 1;
  149.       }
  150.     }
  151.     for (int p = 0; p < N; p++) {
  152.       for (int q = 0; q < N; q++) {
  153.         out.print(val[p][q] + " ");
  154.       }
  155.       out.println();
  156.     }
  157.   }
  158.  
  159.   int N;              // number of competitors
  160.   boolean[][] beats;  // beats[a][b] = true if a beats b in a match
  161. }
  162.  
  163.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:4: error: class D is public, should be declared in a file named D.java
public class D implements Runnable {
       ^
Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
1 error
stdout
copy 
Standard output is empty
https://ideone.com/9bkbmw
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!