結果
| 問題 | No.133 カードゲーム |
| ユーザー |
 nishi5451
|
| 提出日時 | 2021-07-27 20:18:47 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 53 ms / 5,000 ms |
| コード長 | 4,709 bytes |
| コンパイル時間 | 2,545 ms |
| コンパイル使用メモリ | 82,020 KB |
| 実行使用メモリ | 37,308 KB |
| 最終ジャッジ日時 | 2024-07-23 17:34:01 |
| 合計ジャッジ時間 | 4,449 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 19 |
ソースコード
import java.util.*;import java.io.*;public class Main {static final int INF = 1<<30;static final long INFL = 1L<<60;static final int MOD = 1000000007;static final int MOD2 = 998244353;static List<List<Integer>> g;static boolean nextPermutation(int[] arr){for(int i = arr.length-1; i > 0; i--){if(arr[i-1] < arr[i]){int left = i-1, right = arr.length;while(right - left > 1){int mid = (left + right) / 2;if(arr[mid] > arr[i-1]) left = mid;else right = mid;}int tmp = arr[left];arr[left] = arr[i-1];arr[i-1] = tmp;Arrays.sort(arr, i, arr.length);return true;}}return false;}public static void main(String[] args) {FastScanner fs = new FastScanner();PrintWriter pw = new PrintWriter(System.out);int n = fs.nextInt();int[] a = fs.nextInts(n);int[] b = fs.nextInts(n);int[] pa = new int[n];int[] pb = new int[n];double ans = 0;double cnt = 0;for(int i = 0; i < n; i++) pa[i] = i;do{for(int i = 0; i < n; i++) pb[i] = i;do{cnt++;int win = 0;for(int i = 0; i < n; i++){if(a[pa[i]] > b[pb[i]]) win++;}if(win > n/2) ans++;}while(nextPermutation(pb));}while(nextPermutation(pa));pw.println(ans/cnt);pw.close();}}class Util{static void print(int[] arr) {System.out.print("[");for(int i = 0; i < arr.length; i++){if(i == arr.length-1) System.out.println(arr[i] + "]");else System.out.print(arr[i] + ", ");}}static void print(long[] arr) {System.out.print("[");for(int i = 0; i < arr.length; i++){if(i == arr.length-1) System.out.println(arr[i] + "]");else System.out.print(arr[i] + ", ");}}static void print(char[] arr) {System.out.print("[");for(int i = 0; i < arr.length; i++){if(i == arr.length-1) System.out.println(arr[i] + "]");else System.out.print(arr[i] + ", ");}}static void print(double[] arr) {System.out.print("[");for(int i = 0; i < arr.length; i++){if(i == arr.length-1) System.out.println(arr[i] + "]");else System.out.print(arr[i] + ", ");}}static void print(Integer[] arr) {System.out.print("[");for(int i = 0; i < arr.length; i++){if(i == arr.length-1) System.out.println(arr[i] + "]");else System.out.print(arr[i] + ", ");}}static void print(Long[] arr) {System.out.print("[");for(int i = 0; i < arr.length; i++){if(i == arr.length-1) System.out.println(arr[i] + "]");else System.out.print(arr[i] + ", ");}}static void print(String[] arr) {System.out.print("[");for(int i = 0; i < arr.length; i++){if(i == arr.length-1) System.out.println(arr[i] + "]");else System.out.print(arr[i] + ", ");}}}class FastScanner {private InputStream in = System.in;private byte[] buffer = new byte[1024];private int length = 0, p = 0;private boolean hasNextByte() {if (p < length) return true;else{p = 0;try{length = in.read(buffer);}catch(Exception e){e.printStackTrace();}if(length == 0) return false;}return true;}private int readByte() {if (hasNextByte() == true) return buffer[p++];return -1;}private static boolean isPrintable(int n) {return 33 <= n && n <= 126;}private void skip() {while (hasNextByte() && !isPrintable(buffer[p])) p++;}public boolean hasNext() {skip();return hasNextByte();}public String next() {if(!hasNext()) throw new NoSuchElementException();StringBuilder sb = new StringBuilder();int temp = readByte();while (isPrintable(temp)) {sb.appendCodePoint(temp);temp = readByte();}return sb.toString();}public int nextInt() {return Math.toIntExact(nextLong());}public int[] nextInts(int n) {int[] ar = new int[n];for (int i = 0; i < n; i++) ar[i] = nextInt();return ar;}public long[] nextLongs(int n) {long[] ar = new long[n];for (int i = 0; i < n; i++) ar[i] = nextLong();return ar;}public long nextLong() {if(!hasNext()) throw new NoSuchElementException();boolean minus = false;int temp = readByte();if (temp == '-') {minus = true;temp = readByte();}if (temp < '0' || '9' < temp) throw new NumberFormatException();long n = 0;while (isPrintable(temp)) {if ('0' <= temp && temp <= '9') {n *= 10;n += temp - '0';}temp = readByte();}return minus ? -n : n;}public char[] nextChars() {String s = next();return s.toCharArray();}public char[][] nextCharMat(int h, int w) {char[][] ar = new char[h][w];for(int i = 0; i < h; i++){String s = next();for(int j = 0; j < w; j++){ar[i][j] = s.charAt(j);}}return ar;}}