結果

問題 No.1743 Permutation Code
ユーザー whileTrue398whileTrue398
提出日時 2021-11-30 10:33:56
言語 Java21
(openjdk 21)
結果
TLE  
実行時間 -
コード長 12,716 bytes
コンパイル時間 2,668 ms
コンパイル使用メモリ 82,728 KB
実行使用メモリ 63,828 KB
最終ジャッジ日時 2023-09-16 02:25:23
合計ジャッジ時間 13,807 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 121 ms
54,616 KB
testcase_01 AC 114 ms
54,260 KB
testcase_02 AC 112 ms
54,096 KB
testcase_03 AC 122 ms
54,072 KB
testcase_04 AC 211 ms
57,412 KB
testcase_05 AC 127 ms
54,212 KB
testcase_06 AC 338 ms
60,908 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 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Queue;



public class Main {

	static final int inf = Integer.MAX_VALUE / 2;
	static StringBuilder out = new StringBuilder();



	static boolean[] dig;
	static int n, ln;
	static int[] imos;
	static int[][] order;
	static Map<Long, Integer> zeromap = new HashMap<>();
	static List<Queue<Integer>> index = new ArrayList<>();
	static SegmentTree st;
	public static void main(String[] args) {
		FastScanner sc = new FastScanner(System.in);

		/*
		 * 枝刈り法をベースに解く
		 * 0の位置をもとに0の多い数から順列に当てはめていく
		 * その位置のbitをまだ使ってないかは区間和のセグ木で判定する
		 * その区間の和が０ならまだ使ってないので使い、区間の値を全て1にする。
		 */

		//入力を桁ごとにboolで受け取る
		{
		    char[] c = sc.next().toCharArray();
		    n = c.length;
		    //最後に番兵をつける
		    dig = new boolean[n+1];
		    dig[n] = true;

		    imos = new int[n+1];

		    for(int i = 0; i < n; i++) {
		        dig[i] = c[i] == '1';
		        imos[i+1] = imos[i] + (dig[i] ? 1 : 0);
		    }

		}

		// ln =順列の最大値+1
		{
			int cnt = 0;
			for(ln = 1; cnt < n; ln++) {
				int ii = ln;
				while(ii > 0) {
					ii >>= 1;
		    		cnt++;
				}
			}
		}

		//探索する優先順位
		order = new int[ln-1][3];
		for(int i = 0; i+1 < ln; i++) {
			int maxConsecutiveZeros = 0;
			int ConsecutiveZeros = 0;
			int cntZeros = 0;
			int ii = i+1;
			while(ii > 0) {
				if((1&ii) == 1) {
					maxConsecutiveZeros = Math.max(ConsecutiveZeros, maxConsecutiveZeros);
					ConsecutiveZeros = 0;
				}else {
					ConsecutiveZeros++;
					cntZeros++;
				}
				ii >>= 1;
			}

			order[i][0] = i+1;
			order[i][1] = cntZeros;
			order[i][2] = maxConsecutiveZeros;
		}
		//連続した0の数が多いほど優先する
		//それが同じなら0の数が多いほど優先する
		//それも同じならその数の大きい順
		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(y[2], x[2]));


		//すべての0始まり0終わりのパターン(正規表現で'(0+1+)*0+')を抽出し、連続した値に変換するmapを作る
		int mapsize = 0;
		{
		    for(int i = 1; i < ln; i++){
		        int ii = i;
		        while((1&ii) == 1)
		            ii >>= 1;
		        if(ii == 0)
		            continue;

		        long key = 0;
		        int cntz = 0;
		        int cnto = 0;


		        while((1 & ii) == 0){
		            ii >>= 1;
		            key++;
		        }

		        while((1 & ii) == 1){
		            ii >>= 1;
		            cnto++;
		        }

		        long v = 16;
		        while(ii > 0){
		            while((1 & ii) == 0){
		                ii >>= 1;
		                cntz++;
		            }

		            key += cnto*v;
		            v <<= 4;
		            key += cntz*v;
		            v <<= 4;

		            cntz = 0;
		            cnto = 0;

		            while((1 & ii) == 1){
		                ii >>= 1;
		                cnto++;
		            }
		        }

		        if(!zeromap.containsKey(key))
		            zeromap.put(key, mapsize++);
		    }
		}

//		System.out.println("zeromap : ");
//		for(long key : zeromap.keySet()) {
//
//			Deque<Integer> kl = new ArrayDeque<>();
//			String rekey = key + "(1";
//
//			long tkey = key;
//			while(tkey > 0) {
//				kl.push((int)(tkey%16));
//				tkey /= 16;
//			}
//
//			boolean odd = false;
//			while(!kl.isEmpty()) {
//				int tmp = kl.pollFirst();
//				for(int i = 0; i < tmp; i++)
//					rekey += odd ? '1' : '0';
//
//				odd = !odd;
//			}
//
//			rekey += ") -> " + zeromap.get(key);
//
//			System.out.println(rekey);
//		}
//		System.out.println("");

		//入力に出てくる
		//直前に1のある0から始まり、直後に1のある0で終わるパターン
		//(正規表現で'10+(1+0*)*1')の位置を記録
		for(int i = 0; i < mapsize; i++)
		    index.add(new ArrayDeque<>());

		for(int l = 1; l < n; l++){
		    if(dig[l-1] != true || dig[l] != false)
		        continue;

		    long key = 0;
		    boolean prev = false;
		    int cntz = 0;
		    int cnto = 0;
		    long now = 1;
		    for(int r = l; r < n; r++){
		    	now <<= 1;
		    	if(dig[r])
		    		now++;

		        if(now >= ln)
		            break;

		        if(prev != dig[r]) {
		        	if(dig[r])
		        		cnto = 0;
		        	else
		        		cntz = 0;

		        	prev = dig[r];
		        }

		        if(dig[r]){
	                cnto++;
	            }else{
	                cntz++;
	                if(dig[r+1] == true) {
	                	key <<= 4;
	                	key += cnto;
	                	key <<= 4;
	                	key += cntz;
	                	index.get(zeromap.get(key)).add(l);
	                }
	            }
		    }
		}

//		System.out.println("index:");
//		for(int i = 0; i < index.size(); i++) {
//			String str = "" + i + " ->";
//			int qs = index.get(i).size();
//			for(int j = 0; j < qs; j++) {
//				int t = index.get(i).poll();
//				str += " " + t;
//				index.get(i).add(t);
//			}
//			System.out.println(str);
//		}
//		System.out.println("");

		st = new SegmentTree(n);
		if(!dfs(0)) {
			System.out.println(-1);
			return;
		}

		for(int i = 0; i < n; i++) {
			st.getsum(i, i+1);
		}

		Arrays.sort(order, (x, y) -> Integer.compare(x[1], y[1]));
		String ans = "";
		String anss = "";

		int indcnt = 0;
		for(int i = 0; i < order.length; i++) {
			out.append(order[i][0] + " ");
			String an = "";
			int tmp = order[i][0];
			int cnt = 0;
			while(tmp > 0) {
				if((1&tmp) == 1)
					an = '1' + an;
				else
					an = '0' + an;

				tmp >>= 1;
	            cnt++;
			}
			anss += an;
			an = "(" + order[i][0] + ":" + indcnt + ")" + an;
			indcnt += cnt;
			ans += an;
		}

//		System.out.println(anss);
//		System.out.println(ans);
		System.out.println(out);
	}


	private static boolean dfs(int ind) {
		if(ind == order.length) {
			return true;
		}

		long key = 0;
		int lo = 0;
		int bitSize = 0;
		int bitCount = 0;
		int p = order[ind][0];
		while((1&p) == 1) {
			p >>= 1;
	        bitSize++;
	        bitCount++;
		}

		if(p > 0) {
			int cntz = 0;
	        int cnto = 0;


	        while((1 & p) == 0){
	            p >>= 1;
	            bitSize++;
	            key++;
	        }

	        while((1 & p) == 1){
	            p >>= 1;
		    	bitSize++;
		    	bitCount++;
	            cnto++;
	            lo++;
	        }

	        long v = 16;
	        while(p > 0){
	            while((1 & p) == 0){
	                p >>= 1;
		            bitSize++;
	                cntz++;
	            }

	            key += cnto*v;
	            v <<= 4;
	            key += cntz*v;
	            v <<= 4;

	            cntz = 0;
	            cnto = 0;
	            lo = 0;

	            while((1 & p) == 1){
	                p >>= 1;
	            	bitSize++;
	            	bitCount++;
	                cnto++;
	                lo++;
	            }
	        }
		}

//		String str = order[ind][0] + "(" + Integer.toString(order[ind][0], 2) + ") key=" + key;
//		System.out.println(str);

		//二進数表記で0が含まれていない場合
		if(key == 0) {
			for(int i = 0; i < n; i++) {
				if(i+bitSize > n)
					continue;
				if(!dig[i+bitSize])
					continue;
				if(imos[i+bitSize] - imos[i] != bitSize)
					continue;

				if(st.getsum(i, i+bitSize) == 0) {
					st.set(i, i+bitSize, 1);

					order[ind][1] = i;
					if(dfs(ind+1))
						return true;

					st.set(i, i+bitSize, 0);
				}
			}
		}else {
			int inkey = zeromap.get(key);
			int qsize = index.get(inkey).size();
			for(int i = 0; i < qsize; i++) {
				int tmp = index.get(inkey).poll();

				int l = tmp-lo;
				int r = l+bitSize-1;

				if(l >= 0 && r < n)
					if(dig[r+1])
						if(imos[r+1] - imos[l] == bitCount)
							if(st.getsum(l, r+1) == 0) {
								st.set(l, r+1, 1);

								order[ind][1] = l;
								if(dfs(ind+1))
									return true;

								st.set(l, r+1, 0);
							}

				index.get(inkey).add(tmp);
			}
		}


		return false;
	}

}

class SegmentTree {
	private int n;
	int[] node;

	SegmentTree(int size){
		n = 1;
		while(n < size)
			n *= 2;

		node = new int[2*n-1];
	}

	void set(int a, int b, int x){
		set(a, b, x, 0, 0, -1);
	}
	private void set(int a, int b, int x, int k, int l, int r) {
		if(r < 0)
			r = n;

		if(b <= l || r <= a)
			return;

		if(l+1 == r) {
			node[k] = x;
		}else {
			set(a, b, x, 2*k+1, l, (l+r)/2);
			set(a, b, x, 2*k+2, (l+r)/2, r);
			node[k] = node[2*k+1] + node[2*k+2];
		}
	}

	int getsum(int a, int b) {
		return getsum(a, b, 0, 0, -1);
	}
	private int getsum(int a, int b, int k, int l, int r) {
		if(r < 0)
			r = n;
		if(b <= l || r <= a)
			return 0;

		if(a <= l && r <= b)
			return node[k];

		int vl = getsum(a, b, 2*k+1, l, (l+r)/2);
		int vr = getsum(a, b, 2*k+2, (l+r)/2, r);

		return vl + vr;
	}
}

//class SegmentTree {
//	private int n;
//	int[] node, lazy;
//	int inf = Integer.MAX_VALUE/2;
//
//
//	SegmentTree(int size){
//		n = 1;
//		while(n < size)
//			n *= 2;
//
//		node = new int[n*2-1];
//		lazy = new int[n*2-1];
//
//		Arrays.fill(lazy, inf);
//	}
//
//	private void eval(int k, int l, int r) {
//		if(lazy[k] != inf) {
//			node[k] = lazy[k];
//
//			if(l+1 < r) {
//				lazy[2*k+1] += lazy[k] /2;
//				lazy[2*k+2] += lazy[k] /2;
//			}
//
//			lazy[k] = inf;
//		}
//	}
//
//	void set(int a, int b, int x) {
//		set(a, b, x, 0, 0, -1);
//	}
//	private void set(int a, int b, int x, int k, int l, int r) {
//		if(r < 0)
//			r = n;
//
//		eval(k, l, r);
//
//		if(b <= l || r <= a)
//			return;
//
//		if(a <= l && r <= b) {
//			lazy[k] = (r-l)*x;
//			eval(k, l, r);
//		}else {
//			set(a, b, x, 2*k+1, l, (l+r)/2);
//			set(a, b, x, 2*k+2, (l+r)/2, r);
//			node[k] = node[2*k+1] + node[2*k+2];
//		}
//
//
//	}
//
//	int getsum(int a, int b) {
//		return getsum(a, b, 0, 0, -1);
//	}
//	private int getsum(int a, int b, int k, int l, int r) {
//		if(r < 0)
//			r = n;
//		if(b <= l || r <= a)
//			return 0;
//
//		eval(k, l, r);
//		if(a <= l && r <= b)
//			return node[k];
//
//		int vl = getsum(a, b, 2*k+1, l, (l+r)/2);
//		int vr = getsum(a, b, 2*k+2, (l+r)/2, r);
//
//		return vl+vr;
//	}
//}



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