結果
問題 | No.1854 Limited Bubble Sort |
ユーザー |
👑 |
提出日時 | 2022-02-25 23:27:12 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 527 ms / 2,000 ms |
コード長 | 4,888 bytes |
コンパイル時間 | 1,667 ms |
コンパイル使用メモリ | 161,452 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-22 14:25:48 |
合計ジャッジ時間 | 6,091 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 25 |
ソースコード
import std.conv, std.functional, std.range, std.stdio, std.string;import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;import core.bitop;class EOFException : Throwable { this() { super("EOF"); } }string[] tokens;string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }int readInt() { return readToken.to!int; }long readLong() { return readToken.to!long; }real readReal() { return readToken.to!real; }bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1;(unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }int[] solve(int[] P) {const N = cast(int)(P.length);int[] cuts;cuts ~= -1;foreach (i; 0 .. N) if (P[i] == i) {cuts ~= i;}cuts ~= N;const len = cast(int)(cuts.length) - 1;auto ps = P.dup;foreach (j; 0 .. len) {ps[cuts[j] + 1 .. cuts[j + 1]].sort;}foreach (i; 0 .. N) {if (ps[i] != i) {return [-1];}}ps = P.dup;int[] ans;void oper(int i) {assert(0 <= i); assert(i < N - 1);assert(ps[i] != i);assert(ps[i + 1] != i + 1);swap(ps[i], ps[i + 1]);ans ~= i;}auto ls = new int[N + 1];auto rs = new int[N + 1];void update() {ls[0] = -1;foreach (i; 0 .. N) {ls[i + 1] = max(ls[i], ps[i]);}rs[N] = N;foreach_reverse (i; 0 .. N) {rs[i] = min(ps[i], rs[i + 1]);}}update();bool isGood(int i) {const a = ps[i];const b = ps[i + 1];bool ret = true;ret = ret && (a != i);ret = ret && (b != i + 1);if (a == i + 1) {if (b == i) {ret = ret && (ls[i] < b && a < rs[i + 2]);} else {ret = ret && (ls[i] < a && a < rs[i + 2]);}} else {if (b == i) {ret = ret && (ls[i] < b && b < rs[i + 2]);} else {//}}return ret;}foreach (x; 0 .. N) {int pos;foreach (i; 0 .. N) {if (ps[i] == x) {pos = i;break;}}void go(int i) {if (!isGood(i)) {go(i - 1);}assert(isGood(i));oper(i);update();}foreach_reverse (i; x .. pos) {go(i);}}for (; ; ) {bool upd;foreach (i; 0 .. N - 1) {}if (!upd) {break;}}foreach (i; 0 .. N) {assert(ps[i] == i, format("%s: %s %s", P, ans, ps));}return ans;}void main() {debug {foreach (n; 1 .. 6 + 1) {DList!(int[]) que;bool[string] vis;auto start = iota(n).array;vis[start.to!string] = true;que ~= start;for (; !que.empty; ) {auto ps = que.front;que.removeFront;foreach (i; 0 .. n - 1) {if (ps[i + 1] != i && ps[i] != i + 1) {auto qs = ps.dup;swap(qs[i], qs[i + 1]);const key = qs.to!string;if (key !in vis) {vis[key] = true;que ~= qs;}}}}int cnt;auto perm = iota(n).array;do {const res = solve(perm);if (perm.to!string in vis) {assert(res != [-1]);} else {assert(res == [-1]);++cnt;writeln(perm);int[] cuts;cuts ~= -1;foreach (i; 0 .. n) if (perm[i] == i) cuts ~= i;cuts ~= n;auto ps = perm.dup;foreach (j; 0 .. cast(int)(cuts.length) - 1) {ps[cuts[j] + 1 .. cuts[j + 1]].sort;}bool good = true;foreach (i; 0 .. n) good = good && (ps[i] == i);assert(!good);}} while (perm.nextPermutation);writeln(n, ": ", cnt);}}try {for (; ; ) {const numCases = readInt;foreach (caseId; 0 .. numCases) {const N = readInt;auto P = new int[N];foreach (i; 0 .. N) {P[i] = readInt - 1;}const ans = solve(P);if (ans == [-1]) {writeln(-1);} else {writeln(ans.length);foreach (index, i; ans) {if (index) write(" ");write(i + 1);}writeln;}}}} catch (EOFException e) {}}