Submission #989568
Source Code Expand
import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; public class Main { static InputStream is; static PrintWriter out; static String INPUT = ""; static void solve() { int n = ni(); char[] s = ns(n); char[] t = ns(n); if(Arrays.equals(s, t)){ out.println(0); return; } int low = 0, high = 1000005; while(high-low>1){ int h = high+low>>1; if(ok(h, s, t)){ high = h; }else{ low = h; } } if(high > 1000001){ out.println(-1); }else{ out.println(high); } } static boolean ok(int h, char[] s, char[] t) { int p = 0; int[] cs = new int[s.length+3]; int qh = 0; int qt = 0; int[] rs = new int[s.length+3]; int de = 0; for(int i = 0;i < t.length;i++){ if(i > 0 && t[i] == t[i-1]){ if(i-2 < 0 || t[i-2] != t[i]){ rs[qh-1] = h-1+de; cs[qh-1]--; rs[qh] = h+de; cs[qh++] = i+1-de; }else{ cs[qh-1]++; } }else{ while(true){ while(p < s.length && t[i] != s[p])p++; if(p > i || s[p] != t[i])return false; int lastr = -99999; while(qt < qh && cs[qt]+de <= p){ lastr = rs[qt]-de; qt++; } if(lastr != -99999)qt--; if(lastr != -99999 && rs[qt]-de == 0){ p++; continue; } de++; rs[qh] = h+de; cs[qh++] = i+1-de; break; } } // if(h == 1){ // tr(rs); // tr(cs); // } } return true; } public static int sumFenwick(int[] ft, int i) { int sum = 0; for(i++;i > 0;i -= i&-i)sum += ft[i]; return sum; } public static void addFenwick(int[] ft, int i, int v) { if(v == 0 || i < 0)return; int n = ft.length; for(i++;i < n;i += i&-i)ft[i] += v; } public static void main(String[] args) throws Exception { long S = System.currentTimeMillis(); is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); solve(); out.flush(); long G = System.currentTimeMillis(); tr(G-S+"ms"); } private static boolean eof() { if(lenbuf == -1)return true; int lptr = ptrbuf; while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false; try { is.mark(1000); while(true){ int b = is.read(); if(b == -1){ is.reset(); return true; }else if(!isSpaceChar(b)){ is.reset(); return false; } } } catch (IOException e) { return true; } } private static byte[] inbuf = new byte[1024]; static int lenbuf = 0, ptrbuf = 0; private static int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } // private static boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); } private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private static double nd() { return Double.parseDouble(ns()); } private static char nc() { return (char)skip(); } private static String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private static char[] ns(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while(p < n && !(isSpaceChar(b))){ buf[p++] = (char)b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } private static char[][] nm(int n, int m) { char[][] map = new char[n][]; for(int i = 0;i < n;i++)map[i] = ns(m); return map; } private static int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private static int ni() { int num = 0, b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); } }
Submission Info
Submission Time | |
---|---|
Task | F - Shik and Copying String |
User | uwi |
Language | Java8 (OpenJDK 1.8.0) |
Score | 1500 |
Code Size | 4997 Byte |
Status | AC |
Exec Time | 678 ms |
Memory | 108260 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1500 / 1500 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example0.txt, example1.txt, example2.txt, example3.txt |
All | 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, 050.txt, 051.txt, 052.txt, 053.txt, 054.txt, 055.txt, 056.txt, 057.txt, 058.txt, example0.txt, example1.txt, example2.txt, example3.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
000.txt | AC | 96 ms | 8144 KB |
001.txt | AC | 95 ms | 8148 KB |
002.txt | AC | 95 ms | 8148 KB |
003.txt | AC | 97 ms | 8020 KB |
004.txt | AC | 98 ms | 8016 KB |
005.txt | AC | 97 ms | 8016 KB |
006.txt | AC | 97 ms | 8016 KB |
007.txt | AC | 97 ms | 8016 KB |
008.txt | AC | 96 ms | 8148 KB |
009.txt | AC | 97 ms | 8016 KB |
010.txt | AC | 101 ms | 8532 KB |
011.txt | AC | 101 ms | 8656 KB |
012.txt | AC | 102 ms | 8532 KB |
013.txt | AC | 100 ms | 8400 KB |
014.txt | AC | 101 ms | 8532 KB |
015.txt | AC | 102 ms | 8660 KB |
016.txt | AC | 103 ms | 8660 KB |
017.txt | AC | 101 ms | 8660 KB |
018.txt | AC | 102 ms | 8656 KB |
019.txt | AC | 101 ms | 8532 KB |
020.txt | AC | 99 ms | 8276 KB |
021.txt | AC | 101 ms | 8660 KB |
022.txt | AC | 104 ms | 8656 KB |
023.txt | AC | 100 ms | 8276 KB |
024.txt | AC | 100 ms | 8532 KB |
025.txt | AC | 133 ms | 12500 KB |
026.txt | AC | 580 ms | 98948 KB |
027.txt | AC | 511 ms | 99436 KB |
028.txt | AC | 645 ms | 91428 KB |
029.txt | AC | 678 ms | 108240 KB |
030.txt | AC | 479 ms | 99496 KB |
031.txt | AC | 430 ms | 91604 KB |
032.txt | AC | 463 ms | 99568 KB |
033.txt | AC | 488 ms | 99760 KB |
034.txt | AC | 482 ms | 99608 KB |
035.txt | AC | 476 ms | 99456 KB |
036.txt | AC | 479 ms | 91932 KB |
037.txt | AC | 462 ms | 91812 KB |
038.txt | AC | 522 ms | 99712 KB |
039.txt | AC | 469 ms | 91676 KB |
040.txt | AC | 552 ms | 91504 KB |
041.txt | AC | 576 ms | 99204 KB |
042.txt | AC | 582 ms | 108260 KB |
043.txt | AC | 558 ms | 99172 KB |
044.txt | AC | 567 ms | 99232 KB |
045.txt | AC | 608 ms | 91472 KB |
046.txt | AC | 604 ms | 95788 KB |
047.txt | AC | 498 ms | 83556 KB |
048.txt | AC | 530 ms | 83764 KB |
049.txt | AC | 522 ms | 91260 KB |
050.txt | AC | 219 ms | 82516 KB |
051.txt | AC | 217 ms | 82388 KB |
052.txt | AC | 219 ms | 82512 KB |
053.txt | AC | 514 ms | 91748 KB |
054.txt | AC | 487 ms | 99220 KB |
055.txt | AC | 472 ms | 91244 KB |
056.txt | AC | 482 ms | 84220 KB |
057.txt | AC | 505 ms | 91268 KB |
058.txt | AC | 520 ms | 91164 KB |
example0.txt | AC | 97 ms | 8020 KB |
example1.txt | AC | 97 ms | 8148 KB |
example2.txt | AC | 95 ms | 8148 KB |
example3.txt | AC | 97 ms | 8016 KB |