#440941 (C#(csc)) No.1005 BOT対策

提出ソース

結果

問題	No.1005 BOT対策
ユーザー	fgwiebfaoish
提出日時	2020-03-08 10:09:41
言語	C#(csc) (csc 3.9.0)
結果	AC
実行時間	38 ms / 2,000 ms
コード長	6,949 bytes
コンパイル時間	1,276 ms
コンパイル使用メモリ	110,848 KB
実行使用メモリ	19,968 KB
最終ジャッジ日時	2024-11-06 20:18:07
合計ジャッジ時間	3,532 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	35 ms 19,328 KB
testcase_01	AC	35 ms 19,328 KB
testcase_02	AC	35 ms 19,456 KB
testcase_03	AC	34 ms 19,584 KB
testcase_04	AC	22 ms 17,536 KB
testcase_05	AC	34 ms 19,456 KB
testcase_06	AC	23 ms 17,664 KB
testcase_07	AC	23 ms 17,664 KB
testcase_08	AC	23 ms 17,536 KB
testcase_09	AC	24 ms 17,536 KB
testcase_10	AC	37 ms 19,328 KB
testcase_11	AC	38 ms 19,968 KB
testcase_12	AC	35 ms 19,456 KB
testcase_13	AC	35 ms 19,712 KB
testcase_14	AC	35 ms 19,712 KB
testcase_15	AC	35 ms 19,584 KB
testcase_16	AC	34 ms 19,712 KB
testcase_17	AC	34 ms 19,584 KB
testcase_18	AC	22 ms 17,536 KB
testcase_19	AC	23 ms 17,536 KB
testcase_20	AC	23 ms 17,536 KB
testcase_21	AC	34 ms 19,968 KB
testcase_22	AC	35 ms 19,712 KB
testcase_23	AC	37 ms 19,840 KB
testcase_24	AC	35 ms 19,712 KB
testcase_25	AC	35 ms 19,584 KB
testcase_26	AC	35 ms 19,840 KB
testcase_27	AC	22 ms 17,792 KB
testcase_28	AC	35 ms 19,712 KB
testcase_29	AC	35 ms 19,712 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

raw source code

using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
using static Rh;
static class Program{
	const int mod=(int)1e9+7;
	static void Main(){
		Sc sc=new Sc();
		var s=sc.S;
		var t=sc.S;
		int ans=0;
		if(t.Length==1){
			for(int i = 0;i<s.Length;i++) {
				if(t[0]==s[i]){
					Console.WriteLine(-1);
					return;
				}
			}
			Console.WriteLine(0);
			return;
		}
		Rh rh=new Rh();
		var hs=new Hsa(s);
		var ht=t;
		for(int i = t.Length-1;i<s.Length;i++) {
			if(hs.Get(i-t.Length+1,i)==ht){
				ans++;
				i+=t.Length-1;
				if(t[0]==t[t.Length-1]){i--;}
			}
		}
		Console.WriteLine("{0}",ans);
	}
}
public class Rh{
	public static readonly int mod1=1073741783,mod2=1073741789;
	public static readonly int b1=1007,b2=1009+DateTime.Now.Millisecond;
	private static long[] r1,r2;
	private static int n;
	public Rh(){n=0;}
	public Rh(int n){
		Rh.n=n;
		r1=new long[n+1];
		r2=new long[n+1];
		r1[0]=r2[0]=1;
		for(int i = 1;i<=n;i++) {
			r1[i]=(r1[i-1]*b1)%mod1;
			r2[i]=(r2[i-1]*b2)%mod2;
		}
	}
	public class Hsa{
		private Hs[] hs;
		public int n;
		public Hsa(int[] a){
			n=a.Length;
			if(n>Rh.n){
				Rh.n=n;
				r1=new long[n+1];
				r2=new long[n+1];
				r1[0]=r2[0]=1;
				hs=new Hs[n+1];
				hs[0]=new Hs(0);
				for(int i = 1;i<=n;i++) {
					r1[i]=(r1[i-1]*b1)%mod1;
					r2[i]=(r2[i-1]*b2)%mod2;
					hs[i]=hs[i-1]+a[i-1];
				}
			}
			else{
				hs=new Hs[n+1];
				hs[0]=new Hs(0);
				for(int i = 1;i<=n;i++) {hs[i]=hs[i-1]+a[i-1];}
			}
		}
		public Hsa(string a){
			n=a.Length;
			if(n>Rh.n){
				Rh.n=n;
				r1=new long[n+1];
				r2=new long[n+1];
				r1[0]=r2[0]=1;
				hs=new Hs[n+1];
				hs[0]=new Hs(0);
				for(int i = 1;i<=n;i++) {
					r1[i]=(r1[i-1]*b1)%mod1;
					r2[i]=(r2[i-1]*b2)%mod2;
					hs[i]=hs[i-1]+a[i-1];
				}
			}
			else{
				hs=new Hs[n+1];
				hs[0]=new Hs(0);
				for(int i = 1;i<=n;i++) {hs[i]=hs[i-1]+a[i-1];}
			}
		}
		public static implicit operator Hsa(int[] a){return new Hsa(a);}
		public static implicit operator Hsa(string a){return new Hsa(a);}
		public Hs Get(int a,int b){return hs[b+1]-hs[a];}
		public int Bs(int a,int b){return Bs(a,b,n-Max(a,b));}
		public int Bs(int a,int b,int ub){
			int lb=-1,mid=0;
			while(ub-lb>1){
				mid=(ub+lb)/2;
				if(Get(a,a+mid)!=Get(b,b+mid)){ub=mid;}
				else{lb=mid;}
			}
			return ub;
		}
		public int Bsp(Hsa a){return Bsp(0,a);}
		public int Bsp(int k,Hsa a){
			int lb=-1,mid=0,ub=Min(n-k,a.n);
			while(ub-lb>1){
				mid=(ub+lb)/2;
				if(Get(k,mid+k)!=a.Get(0,mid)){ub=mid;}
				else{lb=mid;}
			}
			return ub;
		}
		public int Bss(Hsa a){return Bss(n-1,a);}
		public int Bss(int k,Hsa a){
			int lb=0,mid=0,ub=Min(k+1,a.n)+1;
			while(ub-lb>1){
				mid=(ub+lb)/2;
				if(Get(k+1-mid,k)!=a.Get(a.n-mid,a.n-1)){ub=mid;}
				else{lb=mid;}
			}
			return lb;
		}
	}
	public struct Hs{
		public long h1,h2;
		public int d;
		public Hs(int n){h1=h2=d=0;}
		public static implicit operator bool(Hs h){return h.d>0;}
		public static implicit operator Hs(string s){
			Hs h=new Hs(0);
			for(int i=0;i<s.Length;i++){h+=s[i];}
			return h;
		}
		public static implicit operator Hs(int[] s){
			Hs h=new Hs(0);
			for(int i=0;i<s.Length;i++){h+=s[i];}
			return h;
		}
		public static Hs operator+(Hs a,int c){
			a.h1=(a.h1*b1+c)%mod1;
			a.h2=(a.h2*b2+c)%mod2;
			a.d++;
			return a;
		}
		public static Hs operator+(Hs a,Hs p){
			a.h1=(a.h1*r1[p.d]+p.h1)%mod1;
			a.h2=(a.h2*r2[p.d]+p.h2)%mod2;
			a.d+=p.d;
			return a;
		}
		public static Hs operator-(Hs a,int c){
			a.d--;
			a.h1=(a.h1+mod1-(r1[a.d]*c%mod1))%mod1;
			a.h2=(a.h2+mod2-(r2[a.d]*c%mod2))%mod2;
			return a;
		}
		public static Hs operator-(Hs a,Hs p){
			a.d-=p.d;
			a.h1=(a.h1+mod1-(r1[a.d]*p.h1%mod1))%mod1;
			a.h2=(a.h2+mod2-(r2[a.d]*p.h2%mod2))%mod2;
			return a;
		}
		public static bool operator==(Hs a,Hs b){return a.h1==b.h1&&a.h2==b.h2&&a.d==b.d;}
		public static bool operator!=(Hs a,Hs b){return a.h1!=b.h1||a.h2!=b.h2||a.d!=b.d;}
		public override bool Equals(object obj){return false;}
		public override int GetHashCode(){return 0;}
	}
	public class Hss{
		public int n;
		public Tuple<Hs,int>[] da;
		public Hss(string[] s){
			n=s.Length;
			da=new Tuple<Hs,int>[n];
			for(int i = 0;i<n;i++) {da[i]=Tuple.Create((Hs)s[i],i);}
			Array.Sort(da,(u,v)=>u.Item1.h1.CompareTo(v.Item1.h1));
		}
		public int Eq(Hs h){
			int lb=-1,mid=0,ub=n-1;
			while(ub-lb>1){
				mid=(ub+lb)/2;
				if(da[mid].Item1.h1>=h.h1){ub=mid;}
				else{lb=mid;}
			}
			for(int i = ub;i<n&&da[i].Item1.h1==h.h1;i++) {if(da[i].Item1==h){return da[i].Item2;}}
			return -1;
		}
	}
}
public class Sc{
	public int I{get{return int.Parse(Console.ReadLine());}}
	public long L{get{return long.Parse(Console.ReadLine());}}
	public double D{get{return double.Parse(Console.ReadLine());}}
	public string S{get{return Console.ReadLine();}}
	public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
	public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
	public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
	public string[] Sa{get{return Console.ReadLine().Split();}}
	public object[] Oa{get{return Console.ReadLine().Split();}}
	public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}
	public int[] Ia3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),int.Parse);}
	public int[] Ia3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),int.Parse);}
	public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}
	public long[] La3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),long.Parse);}
	public long[] La3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),long.Parse);}
	public double[] Da2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),double.Parse);}}
	public double[] Da3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),double.Parse);}
	public double[] Da3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),double.Parse);}
	public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;}
	public T[] Arr<T>(int n,Func<int,T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i);}return a;}
	public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Console.ReadLine().Split());}return a;}
	public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Console.ReadLine().Split());}return a;}
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード