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
AC × 4
AC × 63
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