結果
| 問題 |
No.1743 Permutation Code
|
| ユーザー |
 whileTrue398
|
| 提出日時 | 2021-11-30 10:47:24 |
| 言語 | Java (openjdk 23) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 12,619 bytes |
| コンパイル時間 | 4,915 ms |
| コンパイル使用メモリ | 90,328 KB |
| 実行使用メモリ | 53,784 KB |
| 最終ジャッジ日時 | 2024-07-03 04:04:53 |
| 合計ジャッジ時間 | 15,609 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 7 TLE * 1 -- * 22 |
ソースコード
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 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());}
}