結果
問題 | No.927 Second Permutation |
ユーザー |
![]() |
提出日時 | 2019-11-22 22:03:47 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 123 ms / 2,000 ms |
コード長 | 29,052 bytes |
コンパイル時間 | 3,334 ms |
コンパイル使用メモリ | 101,428 KB |
実行使用メモリ | 41,188 KB |
最終ジャッジ日時 | 2024-10-11 03:42:02 |
合計ジャッジ時間 | 6,984 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.io.OutputStream;import java.io.PrintWriter;import java.lang.Character.Subset;import java.math.BigDecimal;import java.text.DecimalFormat;import java.time.temporal.ValueRange;import java.util.AbstractMap;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.Comparator;import java.util.Deque;import java.util.HashMap;import java.util.HashSet;import java.util.List;import java.util.Map;import java.util.Map.Entry;import java.util.Objects;import java.util.PriorityQueue;import java.util.Queue;import java.util.Set;import java.util.Stack;import java.util.TreeMap;import java.util.TreeSet;import java.util.concurrent.ForkJoinPool;import static java.util.Comparator.*;public class Main {public static void main(String[] args) {InputStream inputStream = System.in;OutputStream outputStream = System.out;MyInput in = new MyInput(inputStream);PrintWriter out = new PrintWriter(outputStream);Solver solver = new Solver(in, out);solver.solve();out.close();}// ======================================================================static class Solver {MyInput in;PrintWriter out;public Solver(MyInput in, PrintWriter out) {this.in = in;this.out = out;}// -----------------------------------------public void solve() {String S = ns();int[] C = new int[10];for (int i = 0; i < S.length(); i++) {C[(int)(S.charAt(i) - '0')]++;}int kind = 0, cnt = 0;int sv1 = -1, sv2 = -1;for (int i = 9; i >= 0; i--) {if(C[i] > 0) {kind++;sv2 = sv1;sv1 = i;if(i != 0) cnt += C[i];}}if(kind == 1 || cnt == 1) {prn(-1);return;}String[] X = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"};StringBuffer ans = new StringBuffer();for (int i = 9; i >= 0; i--) {for (int j = 0; j < C[i]; j++) {if(sv2 == i && j == (C[i]-1)) {continue;} else if(sv1 == i && j == 0) {ans.append(X[sv1]).append(X[sv2]);} else {ans.append(X[i]);}}}prn(ans.toString());}// -----------------------------------------// Integer のキーに対して、Integer のカウントを管理する(カウントを足したり、引いたりする)// キーの最大、最小の取得、データの追加、削除も O(long(N)) で処理できる//static class MapCounter {private TreeMap<Integer, Integer> map;// 昇順のマップpublic MapCounter() {map = new TreeMap<>();}// reverse = tree なら降順のマップpublic MapCounter(boolean reverse) {if(reverse) {map = new TreeMap<Integer, Integer>(Collections.reverseOrder());} else {map = new TreeMap<>();}}// キーを追加する(キーが存在すれば、カウントに1足す)public void add(Integer key) {add(key, 1);}public void add(Integer key, int cnt) {Integer val = map.get(key);if(val == null) {map.put(key, cnt);} else {map.put(key, val + cnt);}}// キーを消す(キーが存在すれば、カウントを1減らす)public void remove(Integer key) {sub(key, 1, false);}// キーのカウントを減らすpublic void sub(Integer key) {sub(key, 1);}// キーのカウントから値を引く(マイナスのカウントを許す)public void sub(Integer key, int cnt) {sub(key, cnt, true);}// キーのカウントから値を引く// → マイナスを許可しない場合で、カウントがマイナスになったら消すpublic void sub(Integer key, int cnt, boolean minus) {Integer val = map.get(key);if(val == null) {if(minus) {map.put(key, -cnt); // カウントのマイナスを許す}} else if(val > cnt || minus){map.put(key, val - cnt);} else {map.remove(key);}}// キーのカウントを設定するpublic void set(Integer key, int cnt) {map.put(key, cnt);}// キーのカウントを取得する(なければ NULLを返す)public Integer getCountwithNull(Integer key) {return map.get(key);}// キーのカウントを取得する(なければ 0 を返す)public Integer getCount(Integer key) {Integer val = map.get(key);if(val == null) return 0;else return val;}public Set<Integer> getKey() {return map.keySet();}// 登録されているキーの数を返すpublic int getKeyCount() {return map.keySet().size();}// 先頭キーを返すpublic Integer getFirstKey() {return map.firstKey();}// 最終キーを返すpublic Integer getLastKey() {return map.lastKey();}// マップの初期化public void clear() {map.clear();}}// -----------------------------------------// 配列のバイナリーサーチ 1boolean isRightMin(int[] a, boolean f, int index, int key) {if (f && a[index] >= key) return true; // 以上else if (!f && a[index] > key) return true; // より大きいelse return false;}// 配列 a の中で key 以上(f=true)または、より大きく(f=false)、一番小さい値を返すint binarySearchRightMin(int[] a, boolean f, int key) {int ng = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1int ok = (int)a.length; // 「index = a.length-1」が条件を満たさないこともあるので、初期値は a.length()/* ok と ng のどちらが大きいかわからないことを考慮 */while (Math.abs(ok - ng) > 1) {int mid = (ok + ng) / 2;if (isRightMin(a, f, mid, key)) ok = mid; // 下半分を対象とするelse ng = mid; // 上半分を対象とする}return ok; // ← ここで返すのは isOK() が true の時にセットする方(ok / ng)}// -----------------------------------------// 配列のバイナリーサーチ 2boolean isLeftMax(int[] a, boolean f, int index, int key) {if (f && a[index] <= key) return true; // 以下else if (!f && a[index] < key) return true; // より小さいelse return false;}// 配列 a の中で key 以下(f=true)または、より小さい(f=false)、一番大きい値を返すint binarySearchLeftMax(int[] a, boolean f, int key) {int ng = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1int ok = (int)a.length; // 「index = a.length-1」が条件を満たさないこともあるので、初期値は a.length()/* ok と ng のどちらが大きいかわからないことを考慮 */while (Math.abs(ok - ng) > 1) {int mid = (ok + ng) / 2;if (isLeftMax(a, f, mid, key)) ng = mid; // 上半分を対象とするelse ok = mid; // 下半分を対象とする}return ng; // ← ここで返すのは isOK() が true の時にセットする方(ok / ng)}// -----------------------------------------// オイラーツアー(部分木対応) → 工事中static class EulerTour {Graph g;List<Integer> euler_tour = new ArrayList<>();int[] begin, end;int k = 0, root = 0;void dfs(int v,int p, PrintWriter out) {out.println("v = " + v + " p = " + p);begin[v] = k;euler_tour.add(v);k++;if(!g.contains(v)) {return;}for(int i : g.get(v)) {if(i != p) {dfs(i, v, out);euler_tour.add(v);k++;}}end[v]=k;}// 初期化public void init(int p_cnt, int root, Graph g, PrintWriter out) {begin = new int[p_cnt + 1];end = new int[p_cnt + 1];this.root = root;this.g = g;dfs(root, -1, out);}// 部分木の頂点を渡すと、オイラーツアーの部分木を返すpublic List getPartTour(int v) {return euler_tour.subList(begin[v], end[v]);}// 部分木の頂点を渡すと、頂点のリストを返すpublic List<Integer> getPartList(int v) {Set<Integer> set = new TreeSet<>();set.addAll(getPartTour(v));List<Integer> ans = new ArrayList<>();for(Integer p : set) {ans.add(p);}return ans;}}// -----------------------------------------// 重みなし グラフのリンクリストclass Graph {// 頂点に紐づく頂点のリストprivate Map<Integer, List<Integer>> data = new HashMap<Integer, List<Integer>>();// // 全ての頂点のセット// private Set<Integer> point = new TreeSet<>();// 頂点と頂点の繋がりを追加するvoid add(int from, int to) {List<Integer> list = data.get(from);if(list == null) {list = new ArrayList<Integer>();data.put(from, list);}list.add(to);// point.add(from);// point.add(to);}// 始点から終点が繋がっていれば切るvoid del(int from, int to) {List<Integer> list = data.get(from);if(list == null) {return;}if(list.contains(to)) {list.remove((Object)to);}}// 指定された頂点に紐づく、頂点のリストを返すList<Integer> get(int key) {return data.get(key);}// 頂点 key が登録されているか?boolean contains(int key) {return data.containsKey(key);}// 頂点のセットを返すSet<Integer> keySet() {return data.keySet();}// 頂点 key_1 と 頂点 key_2 が 直接 つながっていれば true を返すboolean isConnect(int key_1, int key_2) {List<Integer> list = data.get(key_1);if(list == null) return false;else return list.contains(key_2);}// 指定された頂点から、すべての頂点への距離を返す(DFS O(N)) → 返り値が 終点と距離のペア のリストList<PP> distList(int key) {List<PP> dist = new ArrayList<>(); // 頂点と距離のペアのリストSet<Integer> mark = new HashSet<>(); // 処理したら入れるStack<PP> stack = new Stack<>(); // スタックの宣言stack.push(new PP(key, 0)); // スタートをスタックに保存while(!stack.isEmpty()) {PP wk = stack.pop(); // スタックから次の頂点を取得int pp = wk.getKey();int dd = wk.getVal();mark.add(pp); // 通過マークdist.add(new PP(pp, dd)); // 距離を登録List<Integer> list = get(pp); // つながっている頂点のリストを取得for(int next : list) {if(mark.contains(next)) continue;stack.push(new PP(next, dd + 1));}}return dist;}// 指定された頂点から、すべての頂点への距離を返す(DFS O(N)) → 返り値は配列int[] distV(int key) {int[] dist = new int[data.keySet().size()+1]; // [頂点] = 距離Arrays.fill(dist, -1); // 届かない場合 -1Set<Integer> mark = new HashSet<>(); // 処理したら入れるStack<PP> stack = new Stack<>(); // スタックの宣言stack.push(new PP(key, 0)); // スタートをスタックに保存while(!stack.isEmpty()) {PP wk = stack.pop(); // スタックから次の頂点を取得int pp = wk.getKey();int dd = wk.getVal();mark.add(pp); // 通過マークdist[pp] = dd; // 距離を登録List<Integer> list = get(pp); // つながっている頂点のリストを取得for(int next : list) {if(mark.contains(next)) continue;stack.push(new PP(next, dd + 1));}}return dist;}Map<Integer, Integer> mapCnt = new HashMap<>(); // 項番(何番目に訪れたか)Map<Integer, Integer> mapLow = new HashMap<>(); // 初期値は項番、つながっている先の項番が小さければコピーする// mapCnt > mapLow なら閉路に含まれる頂点Set<Integer> mark = new HashSet<>(); // 処理したら入れるint number;// mapCnt, mapLow を設定するint bridgeDfs(int now, int pre) {// prn("bridgeDfs now = " + now + " number = " + number);mark.add(now);mapCnt.put(now, number);mapLow.put(now, number);int low;for(int next : get(now)) {if(next == pre) continue;if(mark.contains(next)) {if(mapLow.get(now) > mapLow.get(next)) {// prn(" mapLow[" + now + "] = " + mapLow.get(now)// + " > mapLow[" + next + "] = " + mapLow.get(next));mapLow.put(now, mapLow.get(next));}continue;}number++;low = bridgeDfs(next, now);if(mapLow.get(now) > low) {mapLow.put(now, low);}}return mapLow.get(now);}// 橋の数を返す 先頭の頂点番号を引数とするint bridgeCnt(int start) {mapCnt.clear();mapLow.clear();mark.clear();number = 0;bridgeDfs(start, start);int ans = 0;for(int key : mapCnt.keySet()) {if(mapCnt.get(key) == mapLow.get(key)) {ans++;}}return ans - 1;}// ダンプvoid dump(PrintWriter out) {for(int key : data.keySet()) {out.print(key + " : ");for(int val : data.get(key)) {out.print(val + " ");}out.println("");}}}// -----------------------------------------// 重さを持ったグラフのリンクリストstatic class GraphWith {// キーに紐づくリストに、頂点番号と重さのペアを持つprivate Map<Integer, List<PP>> data = new HashMap<Integer, List<PP>>();// 指定された頂点に紐づく、頂点と重さのペアを追加するvoid add(int key, PP p) {List<PP> list = data.get(key);if(list == null) {list = new ArrayList<PP>();data.put(key, list);}list.add(p);}// 頂点に紐づく、頂点と重さのペアのリストを返すList<PP> get(int key) {return data.get(key);}// 頂点 key が登録されているか?boolean contains(int key) {return data.containsKey(key);}// 頂点のセットを返すSet<Integer> keySet() {return data.keySet();}// 頂点 key_1 と 頂点 key_2 が 直接 つながっていれば true を返すboolean isConnect(int key_1, int key_2) {List<PP> list = data.get(key_1);if(list == null) return false;boolean ans = false;for(PP p : list) {if(p.getKey() == key_2) {ans = true;break;}}return ans;}// 頂点 key_1 と 頂点 key_2 の距離を返す(つながっていなければ Integer.MAX_VALUE)int distance(int key_1, int key_2) {Set<Integer> mark = new HashSet<>(); // 処理したら入れるStack<PP> stack = new Stack<>(); // スタックの宣言stack.push(new PP(key_1, 0)); // スタートをスタックに保存PP wk;int key, val;List<PP> list;while(!stack.isEmpty()) {wk = stack.pop(); // スタックから次の頂点を取得key = wk.getKey();val = wk.getVal();mark.add(key); // 通過マークif(key == key_2) return val;list = get(key); // つながっている頂点のリストを取得if(list == null) continue;for(PP pp : list) {if(mark.contains(pp.getKey())) continue;stack.push(new PP(pp.getKey(), val + pp.getVal()));}}return Integer.MAX_VALUE;}}// -----------------------------------------// 重みなし グラフのリンクリスト(Long)static class GraphLong {private Map<Long, List<Long>> G = new HashMap<Long, List<Long>>();void add(long key, long value) {List<Long> list = G.get(key);if(list == null) {list = new ArrayList<Long>();G.put(key, list);}list.add(value);}List<Long> get(long key) {return G.get(key);}}// -----------------------------------------// 重さを持ったグラフのリンクリスト(Long)static class GraphLongWith {private Map<Long, List<PPL>> G = new HashMap<Long, List<PPL>>();void add(long key, PPL p) {List<PPL> list = G.get(key);if(list == null) {list = new ArrayList<PPL>();G.put(key, list);}list.add(p);}List<PPL> get(long key) {return G.get(key);}}// -----------------------------------------void prn(String s) {out.println(s);}void prn(int i) {out.println(i);}void prn(long i) {out.println(i);}void prr(String s) {out.print(s);}int ni() {return in.nextInt();}long nl() {return in.nextLong();}double nd() {return in.nextDouble();}String ns() {return in.nextString();}int[] ndi(int n) {int[] ans = new int[n];for(int i=0; i < n; i++) {ans[i] = ni();}return ans;}long[] ndl(int n) {long[] ans = new long[n];for(int i=0; i < n; i++) {ans[i] = nl();}return ans;}double[] ndd(int n) {double[] ans = new double[n];for(int i=0; i < n; i++) {ans[i] = nd();}return ans;}String[] nds(int n) {String[] ans = new String[n];for(int i=0; i < n; i++) {ans[i] = ns();}return ans;}int[][] nddi(int n, int m) {int[][] ans = new int[n][m];for(int i=0; i < n; i++) {for(int j=0; j < m; j++) {ans[i][j] = ni();}}return ans;}long[][] nddl(int n, int m) {long[][] ans = new long[n][m];for(int i=0; i < n; i++) {for(int j=0; j < m; j++) {ans[i][j] = nl();}}return ans;}}// Set に入れるなら PPKEY を使う!static class PP{public int key, val;public PP(int key, int val) {this.key = key;this.val = val;}public int getKey() {return key;}public void setKey(int key) {this.key = key;}public int getVal() {return val;}public void setVal(int val) {this.val = val;}}static class PPP{public int key, val1, val2;public PPP(int key, int val1, int val2) {this.key = key;this.val1 = val1;this.val2 = val2;}public int getKey() {return key;}public void setKey(int key) {this.key = key;}public int getVal1() {return val1;}public void setVal1(int val1) {this.val1 = val1;}public int getVal2() {return val2;}public void setVal2(int val2) {this.val2 = val2;}}static class PPL {public long key, val;public PPL(long key, long val) {this.key = key;this.val = val;}public long getKey() {return key;}public void setKey(long key) {this.key = key;}public long getVal() {return val;}public void setVal(long val) {this.val = val;}}static class PPDL {public long key;public long[] val;public PPDL(long key, long[] val) {this.key = key;this.val = val;}public long getKey() {return key;}public void setKey(long key) {this.key = key;}public long[] getVal() {return val;}public void setVal(long[] val) {this.val = val;}public void dump(PrintWriter out) {out.print("key = " + key + " val ");for(int i=0; i < val.length; i++) {out.print("[" + val[i] + "] ");}out.println("");}}// HashMap のキーに使う → Set に入れるのもこれ(PPでは値での比較が行われない)static final class PPKEY {private final int key, val;public PPKEY(int key, int val) {this.key = key;this.val = val;}public int getKey() {return key;}public int getVal() {return val;}@Overridepublic boolean equals(Object obj) {if (obj instanceof PPKEY) {PPKEY dest = (PPKEY) obj;return this.key == dest.key && this.val == dest.val;} else {return false;}}@Overridepublic int hashCode() {return Objects.hash(key, val);}}// HashMap のキーに使う → Set に入れるのもこれ(PPでは値での比較が行われない)static final class PPLKEY{private final long key, val;public PPLKEY(long key, long val) {this.key = key;this.val = val;}public long getKey() {return key;}public long getVal() {return val;}@Overridepublic boolean equals(Object obj) {if (obj instanceof PPKEY) {PPKEY dest = (PPKEY) obj;return this.key == dest.key && this.val == dest.val;} else {return false;}}@Overridepublic int hashCode() {return Objects.hash(key, val);}}// ======================================================================static class Pair<K, V> extends AbstractMap.SimpleEntry<K, V> {/** serialVersionUID. */private static final long serialVersionUID = 6411527075103472113L;public Pair(final K key, final V value) {super(key, value);}}static class MyInput {private final BufferedReader in;private static int pos;private static int readLen;private static final char[] buffer = new char[1024 * 8];private static char[] str = new char[500 * 8 * 2];private static boolean[] isDigit = new boolean[256];private static boolean[] isSpace = new boolean[256];private static boolean[] isLineSep = new boolean[256];static {for (int i = 0; i < 10; i++) {isDigit['0' + i] = true;}isDigit['-'] = true;isSpace[' '] = isSpace['\r'] = isSpace['\n'] = isSpace['\t'] = true;isLineSep['\r'] = isLineSep['\n'] = true;}public MyInput(InputStream is) {in = new BufferedReader(new InputStreamReader(is));}public int read() {if (pos >= readLen) {pos = 0;try {readLen = in.read(buffer);} catch (IOException e) {throw new RuntimeException();}if (readLen <= 0) {throw new MyInput.EndOfFileRuntimeException();}}return buffer[pos++];}public int nextInt() {int len = 0;str[len++] = nextChar();len = reads(len, isSpace);int i = 0;int ret = 0;if (str[0] == '-') {i = 1;}for (; i < len; i++) ret = ret * 10 + str[i] - '0';if (str[0] == '-') {ret = -ret;}return ret;}public long nextLong() {int len = 0;str[len++] = nextChar();len = reads(len, isSpace);int i = 0;long ret = 0L;if (str[0] == '-') {i = 1;}for (; i < len; i++) ret = ret * 10 + str[i] - '0';if (str[0] == '-') {ret = -ret;}return ret;}public double nextDouble() {int len = 0;str[len++] = nextChar();len = reads(len, isSpace);int i = 0;double ret = 0;if (str[0] == '-') {i = 1;}int cnt = 0;for (; i < len; i++) {if(str[i] == '.') {cnt = 10;continue;}if(cnt == 0) {ret = ret * 10 + str[i] - '0';} else {ret = ret + ((double)(str[i] - '0') / cnt);cnt *= 10;}}if (str[0] == '-') {ret = -ret;}return ret;}public String nextString() {String ret = new String(nextDChar()).trim();return ret;}public char[] nextDChar() {int len = 0;len = reads(len, isSpace);char[] ret = new char[len + 1];for (int i=0; i < len; i++) ret[i] = str[i];ret[len] = 0x00;return ret;}public char nextChar() {while (true) {final int c = read();if (!isSpace[c]) {return (char) c;}}}int reads(int len, boolean[] accept) {try {while (true) {final int c = read();if (accept[c]) {break;}if (str.length == len) {char[] rep = new char[str.length * 3 / 2];System.arraycopy(str, 0, rep, 0, str.length);str = rep;}str[len++] = (char) c;}} catch (MyInput.EndOfFileRuntimeException e) {}return len;}static class EndOfFileRuntimeException extends RuntimeException {}}}