#721686 (Java21) No.1743 Permutation Code

提出ソース

結果

問題	No.1743 Permutation Code
ユーザー	whileTrue398
提出日時	2021-12-04 10:40:27
言語	Java21 (openjdk 21)
結果	TLE
実行時間	-
コード長	10,709 bytes
コンパイル時間	3,436 ms
コンパイル使用メモリ	99,396 KB
実行使用メモリ	92,176 KB
最終ジャッジ日時	2023-09-20 20:50:44
合計ジャッジ時間	15,547 ms
ジャッジサーバーID （参考情報）	judge11 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	53 ms 54,564 KB
testcase_01	AC	60 ms 50,380 KB
testcase_02	AC	56 ms 50,396 KB
testcase_03	AC	75 ms 51,628 KB
testcase_04	AC	221 ms 59,208 KB
testcase_05	AC	126 ms 56,596 KB
testcase_06	AC	175 ms 56,720 KB
testcase_07	TLE	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

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());}
}

yukicoder

結果

テストケース

ソースコード