結果
問題 | No.2665 Minimize Inversions of Deque |
ユーザー | tenten |
提出日時 | 2024-03-12 11:29:28 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 564 ms / 2,000 ms |
コード長 | 2,924 bytes |
コンパイル時間 | 2,518 ms |
コンパイル使用メモリ | 93,416 KB |
実行使用メモリ | 67,212 KB |
最終ジャッジ日時 | 2024-09-29 22:15:08 |
合計ジャッジ時間 | 20,261 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
import java.io.*;import java.util.*;import java.util.function.*;import java.util.stream.*;public class Main {public static void main(String[] args) throws Exception {Scanner sc = new Scanner();int t = sc.nextInt();String result = IntStream.range(0, t).mapToObj(p -> {int n = sc.nextInt();BinaryIndexedTree bit = new BinaryIndexedTree(n + 1);Deque<Integer> current = new ArrayDeque<>();int tmp = sc.nextInt();current.addLast(tmp);bit.add(tmp, 1);long count = 0;for (int i = 1; i < n; i++) {int x = sc.nextInt();int left = bit.getSum(x);int right = i - left;if (left < right || (left == right && current.peek() > x)) {current.addFirst(x);count += left;} else {current.addLast(x);count += right;}bit.add(x, 1);}return count + "\n" + current.stream().map(x -> x.toString()).collect(Collectors.joining(" "));}).collect(Collectors.joining("\n"));System.out.println(result);}}class BinaryIndexedTree {int size;int[] tree;public BinaryIndexedTree(int size) {this.size = size;tree = new int[size];}public void add(int idx, int value) {int mask = 1;while (idx < size) {if ((idx & mask) != 0) {tree[idx] += value;idx += mask;}mask <<= 1;}}public int getSum(int from, int to) {return getSum(to) - getSum(from - 1);}public int getSum(int x) {int mask = 1;int ans = 0;while (x > 0) {if ((x & mask) != 0) {ans += tree[x];x -= mask;}mask <<= 1;}return ans;}}class Scanner {BufferedReader br;StringTokenizer st = new StringTokenizer("");StringBuilder sb = new StringBuilder();public Scanner() {try {br = new BufferedReader(new InputStreamReader(System.in));} catch (Exception e) {}}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}public double nextDouble() {return Double.parseDouble(next());}public String next() {try {while (!st.hasMoreTokens()) {st = new StringTokenizer(br.readLine());}} catch (Exception e) {e.printStackTrace();} finally {return st.nextToken();}}}