結果
| 問題 | No.608 God's Maze |
| コンテスト | |
| ユーザー |
 夕叢霧香(ゆうむらきりか)
|
| 提出日時 | 2017-12-08 02:35:02 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,515 bytes |
| 記録 | |
| コンパイル時間 | 2,906 ms |
| コンパイル使用メモリ | 83,276 KB |
| 実行使用メモリ | 45,164 KB |
| 最終ジャッジ日時 | 2024-11-29 05:42:33 |
| 合計ジャッジ時間 | 11,287 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 42 WA * 22 RE * 1 |
ソースコード
import java.io.*;
import java.util.*;
class Main {
static String s;
static int[]zero,one;
static int f(int a,int l,int r,int fs,int fe){
System.err.printf("enter f(%d,%d,%d,%d,%d)\n",a,l,r,fs,fe);
if(fs>=fe){
fs=-1;fe=-1;
}
if(fs==-1){
int m=Integer.MAX_VALUE;
int i1=Arrays.binarySearch(one,r);
if(i1<0)i1=-i1-1;
int i2=Arrays.binarySearch(one,l);
if(i2<0)i2=-i2-1;
if(i1==i2){
return 0;
}
int x=one[i2],y=one[i1-1];
if(x<a)m=Math.min(m,a-x+f(x,x+1,r,x+1,a));
if(a<y)m=Math.min(m,y-a+f(y,l,y,a+1,y));
System.err.println("f("+a+","+l+","+r+")="+m);
return m;
}
int ans;
if(a<l){
int nxt=-1;
System.err.println(Arrays.toString(one) + " r = " + r + " fe = " + fe);
int i1=Arrays.binarySearch(one,r);
if(i1<0)i1=-i1-1;
int i2=Arrays.binarySearch(one,fe);
if(i2<0)i2=-i2-1;
System.err.println("i1="+i1+" i2="+i2);
if(i1>i2){
nxt=one[i1-1];
System.err.println("nxt = " + nxt);
ans=nxt-a+f(nxt,l,nxt,fe,nxt);
}else{
int i3=Arrays.binarySearch(zero,fe);
if(i3<0)i3=-i3-1;
int i4=Arrays.binarySearch(zero,fs);
if(i4<0)i4=-i4-1;
if(i3>i4){
nxt=zero[i3-1];
ans=nxt-a+f(nxt,l,nxt,-1,-1);
}else
ans=0;
}
}else{
int nxt=-1;
int i1=Arrays.binarySearch(one,r);
if(i1<0)i1=-i1-1;
int i2=Arrays.binarySearch(one,l);
if(i2<0)i2=-i2-1;
System.err.println("i1="+i1+" i2="+i2);
if(i1>i2){
nxt=one[i2];
ans=a-nxt+f(nxt,nxt+1,r,nxt+1,fs);
}else{
int i3=Arrays.binarySearch(zero,r);
if(i3<0)i3=-i3-1;
int i4=Arrays.binarySearch(zero,fs);
if(i4<0)i4=-i4-1;
if(i3>i4){
nxt=zero[i4];
ans=a-nxt+f(nxt,nxt+1,r,-1,-1);
}else
ans=0;
}
}
System.err.printf("f(%d,%d,%d,%d,%d)=%d\n",a,l,r,fs,fe,ans);
return ans;
}
static int g(int[]x,int a){
int ans=0;
int[]oldx=x.clone();
int n=x.length;
int p=a;
int last=0;
for(int i=0;i<n;++i)
if(x[i]==1)last=i;
while(true){
int p2=p+1;
while(p2<=last&&x[p2]!=0)p2++;
if(p2==last+1){
ans+=last-p;
break;
}
x[p2]=1;
x[p2+1]=1-x[p2+1];
if(last==p2+1)last=p2;
ans+=p2-p+2;
p=p2;
}
//System.err.println("g("+Arrays.toString(oldx)+","+a+")="+ans);
return ans;
}
public static void main(String[] args) {
MyScanner sc = new MyScanner();
out = new PrintWriter(new BufferedOutputStream(System.out));
int n=sc.nextInt()-1;
s=sc.next();
int l=s.length();
int p=0,q=0;
zero=new int[s.length()];
one=new int[s.length()];
for(int i=0;i<s.length();++i)
if(s.charAt(i)=='.')
zero[p++]=i;
else
one[q++]=i;
zero=Arrays.copyOf(zero,p);
one=Arrays.copyOf(one,q);
int[]t=new int[l];
for(int i=0;i<l;++i)
t[i]=s.charAt(i)=='#'?1:0;
int[]u=t.clone();
int x=one[0],y=one[q-1];
System.err.println("x="+x+" y="+y);
int m=Integer.MAX_VALUE;
if(x<n)
for(int i=x;i<n;++i)u[i]=1-u[i];
m=Math.min(m,Math.max(0,n-x)+g(u,x));
u=t.clone();
if(n<y)
for(int i=n+1;i<=y;++i)u[i]=1-u[i];
for(int i=0;i<l/2;++i){
int temp=u[i];
u[i]=u[l-1-i];
u[l-1-i]=temp;
}
m=Math.min(m,Math.max(0,y-n)+g(u,l-1-y));
out.println(m);
out.close();
}
// http://codeforces.com/blog/entry/7018
//-----------PrintWriter for faster output---------------------------------
public static PrintWriter out;
//-----------MyScanner class for faster input----------
public static class MyScanner {
BufferedReader br;
StringTokenizer st;
public MyScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine(){
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
}