結果

問題 No.2665 Minimize Inversions of Deque
ユーザー ks2mks2m
提出日時 2024-03-08 21:39:47
言語 Java
(openjdk 23)
結果
AC  
実行時間 464 ms / 2,000 ms
コード長 2,903 bytes
コンパイル時間 5,953 ms
コンパイル使用メモリ 80,396 KB
実行使用メモリ 65,996 KB
最終ジャッジ日時 2024-09-29 19:09:05
合計ジャッジ時間 15,900 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
PrintWriter pw = new PrintWriter(System.out);
for (int z = 0; z < t; z++) {
int n = Integer.parseInt(br.readLine());
String[] sa = br.readLine().split(" ");
int[] p = new int[n];
for (int i = 0; i < n; i++) {
p[i] = Integer.parseInt(sa[i]) - 1;
}
long ans = 0;
Deque<Integer> que = new ArrayDeque<>();
FenwickTree ft = new FenwickTree(n);
for (int i = 0; i < n; i++) {
long l = ft.sum(p[i]);
long r = ft.sum(p[i], n);
if (l < r) {
que.addFirst(p[i]);
ans += l;
} else if (l > r) {
que.addLast(p[i]);
ans += r;
} else {
if (que.isEmpty()) {
que.add(p[i]);
} else if (p[i] < que.peekFirst()) {
que.addFirst(p[i]);
ans += l;
} else {
que.addLast(p[i]);
ans += r;
}
}
ft.add(p[i], 1);
}
pw.println(ans);
StringBuilder sb = new StringBuilder();
while (!que.isEmpty()) {
sb.append(que.poll() + 1).append(' ');
}
sb.deleteCharAt(sb.length() - 1);
pw.println(sb.toString());
}
pw.flush();
br.close();
}
}
class FenwickTree {
private int n;
private long[] data;
/**
* na[0]a[n-1]0<br>
* O(n)
*
* @param n
*/
public FenwickTree(int n) {
this.n = n;
data = new long[n];
}
/**
* Fenwick Tree<br>
* O(n)
*
* @param data
*/
public FenwickTree(long[] data) {
this(data.length);
build(data);
}
/**
* a[p] += x <br>
* O(log n)
*
* @param p 0≦pn
* @param x
*/
void add(int p, long x) {
assert 0 <= p && p < n : "p=" + p;
p++;
while (p <= n) {
data[p - 1] += x;
p += p & -p;
}
}
/**
* a[l] + ... + a[r-1] <br>
* O(log n)
*
* @param l 0≦l≦r≦n
* @param r 0≦l≦r≦n
*/
long sum(int l, int r) {
assert 0 <= l && l <= r && r <= n : "l=" + l + ", r=" + r;
return sum(r) - sum(l);
}
/**
* a[0] + ... + a[r-1] <br>
* O(log n)
*
* @param r 0≦r≦n
*/
long sum(int r) {
assert 0 <= r && r <= n : "r=" + r;
long s = 0;
while (r > 0) {
s += data[r - 1];
r -= r & -r;
}
return s;
}
private void build(long[] dat) {
System.arraycopy(dat, 0, data, 0, n);
for (int i = 1; i <= n; i++) {
int p = i + (i & -i);
if (p <= n) {
data[p - 1] += data[i - 1];
}
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0