結果
| 問題 |
No.1743 Permutation Code
|
| ユーザー |
 whileTrue398
|
| 提出日時 | 2021-12-04 10:40:27 |
| 言語 | Java (openjdk 23) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 10,709 bytes |
| コンパイル時間 | 2,513 ms |
| コンパイル使用メモリ | 92,408 KB |
| 実行使用メモリ | 91,244 KB |
| 最終ジャッジ日時 | 2024-07-06 15:38:20 |
| 合計ジャッジ時間 | 13,766 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 7 TLE * 1 -- * 22 |
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
public class Main {
static StringBuilder out = new StringBuilder();
static boolean[] dig, searchedNum;
static int len, n, maxBitsLen;
static int[] canPutNum, bitlen;
static int[][] order;
static Map<Integer, Integer> getOrder = new HashMap<>();
static List<Set<Integer>> numInd = new ArrayList<>();
static List<List<Integer>> indNum = new ArrayList<>();
static boolean[] stopFlag;
public static void main(String[] args) {
FastScanner sc = new FastScanner(System.in);
/*
* DFSを枝刈りして解く
*/
//入力を桁ごとにboolで受け取る
{
char[] c = sc.next().toCharArray();
len = c.length;
//最後に番兵をつける
dig = new boolean[len+1];
dig[len] = true;
for(int i = 0; i < len; i++) {
dig[i] = c[i] == '1';
}
}
// n =順列の最大値+1
{
int cnt = 0;
for(n = 1; cnt < len; n++) {
int ii = n;
while(ii > 0) {
ii >>= 1;
cnt++;
}
}
}
//入力のbit列に置ける位置
canPutNum = new int[n];
for(int i = 0; i < n; i++)
numInd.add(new HashSet<>());
for(int i = 0; i < len; i++)
indNum.add(new ArrayList<>());
for(int l = 0; l < len; l++){
if(!dig[l])
continue;
int tmp = 0;
for(int r = l; r < len; r++) {
tmp <<= 1;
if(dig[r])
tmp++;
if(tmp >= n)
break;
if(!dig[r+1])
continue;
numInd.get(tmp).add(l);
indNum.get(l).add(tmp);
canPutNum[tmp]++;
}
}
//探索する優先順位
order = new int[n-1][3];
bitlen = new int[n];
for(int i = 0; i+1 < n; i++) {
int ConsecutiveZeros = 0;
int cost = 0;
int ii = i+1;
while(ii > 0) {
if((1&ii) == 1) {
cost += ConsecutiveZeros*ConsecutiveZeros;
ConsecutiveZeros = 0;
}else {
ConsecutiveZeros++;
}
bitlen[i+1]++;
ii >>= 1;
}
maxBitsLen = bitlen[n-1];
order[i][0] = i+1;
order[i][1] = cost;
order[i][2] = canPutNum[i+1];
}
/*
* inputのbit列に出現数が少ない->costが大きい->数が大きい
* 順で探索する
* costはbit表記の時に連続した0の数を２乗した和
*
* costが同じなら値が大きいものを優先することで
* 内包されている関係を一方向だけで考えられる
* 13(1101)と5(101)の時、costはどちらも同じになり
* 上記条件により13が先に探索される
*/
Arrays.sort(order, (x, y) -> Integer.compare(y[0], x[0]));
Arrays.sort(order, (x, y) -> Integer.compare(y[1], x[1]));
Arrays.sort(order, (x, y) -> Integer.compare(x[2], y[2]));
for(int i = 0; i+1 < n; i++)
getOrder.put(order[i][0], i);
stopFlag = new boolean[len];
searchedNum = new boolean[n];
if(!dfs(0)) {
System.out.println(-1);
return;
}
//order[i][1]にはその数字を置いた
//indが入っているため降順でansになる
Arrays.sort(order, (x, y) -> Integer.compare(x[1], y[1]));
//答えからbitsを生成
// for(int i = 0; i < order.length; i++) {
// String tmp = "";
// int ii = order[i][0];
// while(ii > 0) {
// if((1&ii) == 1)
// tmp = '1' + tmp;
// else
// tmp = '0' + tmp;
//
// ii >>= 1;
// }
// out.append(tmp);
// }
//
// out.append("\n");
for(int i = 0; i < order.length; i++) {
out.append(order[i][0]);
out.append(' ');
}
System.out.println(out);
}
private static boolean dfs(int depth) {
if(depth == order.length) {
return true;
}
int p = order[depth][0];
//interrupt済なら飛ばす
if(searchedNum[p])
if(dfs(depth+1))
return true;
ArrayList<Integer> indexList = new ArrayList<>(numInd.get(p));
List<Pair> removeList = new ArrayList<>();
List<Integer> interruptList = new ArrayList<>();
for(int l : indexList) {
int r = l+bitlen[p]-1;
boolean f = true;
int lowerLim = 0;
for(int ll = l-1; ll+maxBitsLen > l; ll--) {
if(ll < 0)
break;
lowerLim <<= 1;
lowerLim++;
if(!dig[ll])
continue;
if(stopFlag[ll])
break;
int removeInd = getUpperBound(lowerLim, indNum.get(ll));
int arrSize = indNum.get(ll).size();
for(; removeInd < arrSize; removeInd++) {
int remove = indNum.get(ll).get(removeInd);
if(numInd.get(remove).remove(ll)) {
removeList.add(new Pair(remove, ll));
canPutNum[remove]--;
if(canPutNum[remove] == 0) {
f = false;
break;
}else if(canPutNum[remove] == 1 && !searchedNum[remove]) {
//canPutNumが1で未探索なら位置が確定しているので先に探索する
int interruptInd = new ArrayList<>(numInd.get(remove)).get(0);
if(!interrupt(remove, interruptInd, removeList, interruptList)) {
f = false;
break;
}
order[getOrder.get(remove)][1] = interruptInd;
searchedNum[remove] = true;
interruptList.add(remove);
}
}
}
if(!f)
break;
}
if(f)for(int ll = l; ll <= r; ll++) {
for(int remove : indNum.get(ll)) {
if(remove == p)
continue;
if(numInd.get(remove).remove(ll)) {
removeList.add(new Pair(remove, ll));
canPutNum[remove]--;
if(canPutNum[remove] == 0) {
f = false;
break;
}else if(canPutNum[remove] == 1 && !searchedNum[remove]) {
int interruptInd = new ArrayList<>(numInd.get(remove)).get(0);
if(!interrupt(remove, interruptInd, removeList, interruptList)) {
f = false;
break;
}
order[getOrder.get(remove)][1] = interruptInd;
searchedNum[remove] = true;
interruptList.add(remove);
}
}
}
}
if(f) {
stopFlag[l] = true;
stopFlag[r] = true;
searchedNum[p] = true;
order[depth][1] = l;
if(dfs(depth+1))
return true;
searchedNum[p] = false;
stopFlag[l] = false;
stopFlag[r] = false;
}
for(Pair pair : removeList) {
if(!numInd.get(pair.a).contains(pair.b)) {
numInd.get(pair.a).add(pair.b);
canPutNum[pair.a]++;
}
}
for(int interrupt : interruptList)
searchedNum[interrupt] = false;
}
return false;
}
private static boolean interrupt(int p, int l, List<Pair> removeList, List<Integer> interruptList) {
int r = l+bitlen[p]-1;
boolean f = true;
int lowerLim = 0;
for(int ll = l-1; ll+maxBitsLen > l; ll--) {
if(ll < 0)
break;
lowerLim <<= 1;
lowerLim++;
if(!dig[ll])
continue;
if(stopFlag[ll])
break;
int removeInd = getUpperBound(lowerLim, indNum.get(ll));
int arrSize = indNum.get(ll).size();
for(; removeInd < arrSize; removeInd++) {
int remove = indNum.get(ll).get(removeInd);
if(numInd.get(remove).remove(ll)) {
removeList.add(new Pair(remove, ll));
canPutNum[remove]--;
if(canPutNum[remove] == 0) {
f = false;
break;
}else if(canPutNum[remove] == 1 && !searchedNum[remove]) {
int interruptInd = new ArrayList<>(numInd.get(remove)).get(0);
if(!interrupt(remove, interruptInd, removeList, interruptList)) {
f = false;
break;
}
order[getOrder.get(remove)][1] = interruptInd;
searchedNum[remove] = true;
interruptList.add(remove);
}
}
}
if(!f)
break;
}
if(f)for(int ll = l; ll <= r; ll++) {
for(int remove : indNum.get(ll)) {
if(remove == p)
continue;
if(numInd.get(remove).remove(ll)) {
removeList.add(new Pair(remove, ll));
canPutNum[remove]--;
if(canPutNum[remove] == 0) {
f = false;
break;
}else if(canPutNum[remove] == 1 && !searchedNum[remove]) {
int interruptInd = new ArrayList<>(numInd.get(remove)).get(0);
if(!interrupt(remove, interruptInd, removeList, interruptList)) {
f = false;
break;
}
order[getOrder.get(remove)][1] = interruptInd;
searchedNum[remove] = true;
interruptList.add(remove);
}
}
}
}
return f;
}
private static int getUpperBound(int lowerLim, List<Integer> arr) {
int l = 0;
int r = arr.size()-1;
while(l <= r) {
int m = (l+r)/2;
if(arr.get(m) <= lowerLim)
l = m+1;
else
r = m-1;
}
return l;
}
}
class Pair{
int a, b;
Pair(int a, int b){
this.a = a;
this.b = b;
}
}
class FastScanner {
private final InputStream in = System.in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
public FastScanner(InputStream in2) {
// TODO 自動生成されたコンストラクター・スタブ
}
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
}else{
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
if (buflen <= 0) {
return false;
}
}
return true;
}
private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
public String next() {
if (!hasNext()) throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while(isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public long nextLong() {
if (!hasNext()) throw new NoSuchElementException();
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
if (b < '0' || '9' < b) {
throw new NumberFormatException();
}
while(true){
if ('0' <= b && b <= '9') {
n *= 10;
n += b - '0';
}else if(b == -1 || !isPrintableChar(b)){
return minus ? -n : n;
}else{
throw new NumberFormatException();
}
b = readByte();
}
}
public int nextInt() {
long nl = nextLong();
if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
return (int) nl;
}
public double nextDouble() { return Double.parseDouble(next());}
}