Submission #2211777


Source Code Expand

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-8;
const int inf=1e8;
ll MOD1=134832894;
ll MOD2=183489237;
ll x1=52452452;
ll x2=34567343;
vector<ll>hash1,hash2,X1,X2;
int n;
int f(int i){
	set<pair<ll,ll> >se;
	rep(j,n-i){
		ll a1=(hash1[i+j+1]-hash1[j]+MOD1)%MOD1*X1[n-(i+j+1)]%MOD1;
		ll a2=(hash2[i+j+1]-hash2[j]+MOD2)%MOD2*X2[n-(i+j+1)]%MOD2;
		se.insert(pair<ll,ll>(a1,a2));
	}
	return se.size();
}
int main(){
	string s;
	cin>>s;
	n=s.size();
	X1=X2=vector<ll>(n+1);
	X1[0]=X2[0]=1;
	rep(i,n){
		X1[i+1]=(X1[i]*x1)%MOD1;
		X2[i+1]=(X2[i]*x2)%MOD2;
	}
	hash1=hash2=vector<ll>(n+1);
	rep(i,n){
		hash1[i+1]=(s[i]-'a')*X1[i+1];
		hash2[i+1]=(s[i]-'a')*X2[i+1];
	}
	rep(i,n){
		hash1[i+1]=(hash1[i+1]+hash1[i])%MOD1;
		hash2[i+1]=(hash2[i+1]+hash2[i])%MOD2;
	}
//	rep(i,n){
	int l=0,r=n;
	while(r-l>2){
		int h1=l+(r-l)/3,h2=l+(r-l)/3*2;
//		cout<<l<<" "<<h1<<" "<<h2<<" "<<r<<endl;
		int H1=f(h1),H2=f(h2);
//		cout<<H1<<" "<<H2<<endl;
		if(H1>H2)r=h2;
		else l=h1;
	}
	int out=0;
	loop(i,l,r)out=max(out,f(i));
	cout<<out<<endl;
}
 
 
 
 

Submission Info

Submission Time
Task H - WAAAAAAAAAAAAALL
User vjudge5
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1688 Byte
Status WA
Exec Time 1 ms
Memory 256 KB

Judge Result

Set Name Subtask1 Subtask2 All
Score / Max Score 0 / 30 0 / 30 0 / 140
Status
WA × 37
WA × 36
WA × 107
Set Name Test Cases
Subtask1 00_00_sample.txt, 00_01_sample.txt, 00_02_sample.txt, 00_03_random.txt, 00_04_random.txt, 00_05_random.txt, 00_06_random.txt, 00_07_random.txt, 00_08_random.txt, 00_09_random.txt, 00_10_random.txt, 00_11_random.txt, 00_12_random.txt, 00_13_random.txt, 00_14_random.txt, 00_15_random.txt, 00_16_random.txt, 00_17_random.txt, 00_18_random.txt, 00_19_random.txt, 00_20_random.txt, 00_21_random.txt, 00_22_random.txt, 00_23_freedom.txt, 00_24_freedom.txt, 00_25_freedom.txt, 00_26_full.txt, 00_27_full.txt, 00_28_full.txt, 00_29_min.txt, 00_30_min.txt, 00_31_min.txt, 00_32_max.txt, 00_33_max.txt, 00_34_max.txt, 00_35_max.txt, 00_36_max.txt
Subtask2 01_37_sample.txt, 01_38_sample.txt, 01_39_random.txt, 01_40_random.txt, 01_41_random.txt, 01_42_random.txt, 01_43_random.txt, 01_44_random.txt, 01_45_random.txt, 01_46_random.txt, 01_47_random.txt, 01_48_random.txt, 01_49_random.txt, 01_50_random.txt, 01_51_random.txt, 01_52_random.txt, 01_53_random.txt, 01_54_random.txt, 01_55_random.txt, 01_56_random.txt, 01_57_random.txt, 01_58_random.txt, 01_59_freedom.txt, 01_60_freedom.txt, 01_61_freedom.txt, 01_62_full.txt, 01_63_full.txt, 01_64_full.txt, 01_65_min.txt, 01_66_min.txt, 01_67_min.txt, 01_68_max.txt, 01_69_max.txt, 01_70_max.txt, 01_71_max.txt, 01_72_max.txt
All 00_00_sample.txt, 00_01_sample.txt, 00_02_sample.txt, 00_03_random.txt, 00_04_random.txt, 00_05_random.txt, 00_06_random.txt, 00_07_random.txt, 00_08_random.txt, 00_09_random.txt, 00_10_random.txt, 00_11_random.txt, 00_12_random.txt, 00_13_random.txt, 00_14_random.txt, 00_15_random.txt, 00_16_random.txt, 00_17_random.txt, 00_18_random.txt, 00_19_random.txt, 00_20_random.txt, 00_21_random.txt, 00_22_random.txt, 00_23_freedom.txt, 00_24_freedom.txt, 00_25_freedom.txt, 00_26_full.txt, 00_27_full.txt, 00_28_full.txt, 00_29_min.txt, 00_30_min.txt, 00_31_min.txt, 00_32_max.txt, 00_33_max.txt, 00_34_max.txt, 00_35_max.txt, 00_36_max.txt, 01_37_sample.txt, 01_38_sample.txt, 01_39_random.txt, 01_40_random.txt, 01_41_random.txt, 01_42_random.txt, 01_43_random.txt, 01_44_random.txt, 01_45_random.txt, 01_46_random.txt, 01_47_random.txt, 01_48_random.txt, 01_49_random.txt, 01_50_random.txt, 01_51_random.txt, 01_52_random.txt, 01_53_random.txt, 01_54_random.txt, 01_55_random.txt, 01_56_random.txt, 01_57_random.txt, 01_58_random.txt, 01_59_freedom.txt, 01_60_freedom.txt, 01_61_freedom.txt, 01_62_full.txt, 01_63_full.txt, 01_64_full.txt, 01_65_min.txt, 01_66_min.txt, 01_67_min.txt, 01_68_max.txt, 01_69_max.txt, 01_70_max.txt, 01_71_max.txt, 01_72_max.txt, 02_100_min.txt, 02_101_min.txt, 02_102_max.txt, 02_103_max.txt, 02_104_max.txt, 02_105_max.txt, 02_106_max.txt, 02_73_random.txt, 02_74_random.txt, 02_75_random.txt, 02_76_random.txt, 02_77_random.txt, 02_78_random.txt, 02_79_random.txt, 02_80_random.txt, 02_81_random.txt, 02_82_random.txt, 02_83_random.txt, 02_84_random.txt, 02_85_random.txt, 02_86_random.txt, 02_87_random.txt, 02_88_random.txt, 02_89_random.txt, 02_90_random.txt, 02_91_random.txt, 02_92_random.txt, 02_93_freedom.txt, 02_94_freedom.txt, 02_95_freedom.txt, 02_96_full.txt, 02_97_full.txt, 02_98_full.txt, 02_99_min.txt
Case Name Status Exec Time Memory
00_00_sample.txt WA 1 ms 256 KB
00_01_sample.txt WA 1 ms 256 KB
00_02_sample.txt WA 1 ms 256 KB
00_03_random.txt WA 1 ms 256 KB
00_04_random.txt WA 1 ms 256 KB
00_05_random.txt WA 1 ms 256 KB
00_06_random.txt WA 1 ms 256 KB
00_07_random.txt WA 1 ms 256 KB
00_08_random.txt WA 1 ms 256 KB
00_09_random.txt WA 1 ms 256 KB
00_10_random.txt WA 1 ms 256 KB
00_11_random.txt WA 1 ms 256 KB
00_12_random.txt WA 1 ms 256 KB
00_13_random.txt WA 1 ms 256 KB
00_14_random.txt WA 1 ms 256 KB
00_15_random.txt WA 1 ms 256 KB
00_16_random.txt WA 1 ms 256 KB
00_17_random.txt WA 1 ms 256 KB
00_18_random.txt WA 1 ms 256 KB
00_19_random.txt WA 1 ms 256 KB
00_20_random.txt WA 1 ms 256 KB
00_21_random.txt WA 1 ms 256 KB
00_22_random.txt WA 1 ms 256 KB
00_23_freedom.txt WA 1 ms 256 KB
00_24_freedom.txt WA 1 ms 256 KB
00_25_freedom.txt WA 1 ms 256 KB
00_26_full.txt WA 1 ms 256 KB
00_27_full.txt WA 1 ms 256 KB
00_28_full.txt WA 1 ms 256 KB
00_29_min.txt WA 1 ms 256 KB
00_30_min.txt WA 1 ms 256 KB
00_31_min.txt WA 1 ms 256 KB
00_32_max.txt WA 1 ms 256 KB
00_33_max.txt WA 1 ms 256 KB
00_34_max.txt WA 1 ms 256 KB
00_35_max.txt WA 1 ms 256 KB
00_36_max.txt WA 1 ms 256 KB
01_37_sample.txt WA 1 ms 256 KB
01_38_sample.txt WA 1 ms 256 KB
01_39_random.txt WA 1 ms 256 KB
01_40_random.txt WA 1 ms 256 KB
01_41_random.txt WA 1 ms 256 KB
01_42_random.txt WA 1 ms 256 KB
01_43_random.txt WA 1 ms 256 KB
01_44_random.txt WA 1 ms 256 KB
01_45_random.txt WA 1 ms 256 KB
01_46_random.txt WA 1 ms 256 KB
01_47_random.txt WA 1 ms 256 KB
01_48_random.txt WA 1 ms 256 KB
01_49_random.txt WA 1 ms 256 KB
01_50_random.txt WA 1 ms 256 KB
01_51_random.txt WA 1 ms 256 KB
01_52_random.txt WA 1 ms 256 KB
01_53_random.txt WA 1 ms 256 KB
01_54_random.txt WA 1 ms 256 KB
01_55_random.txt WA 1 ms 256 KB
01_56_random.txt WA 1 ms 256 KB
01_57_random.txt WA 1 ms 256 KB
01_58_random.txt WA 1 ms 256 KB
01_59_freedom.txt WA 1 ms 256 KB
01_60_freedom.txt WA 1 ms 256 KB
01_61_freedom.txt WA 1 ms 256 KB
01_62_full.txt WA 1 ms 256 KB
01_63_full.txt WA 1 ms 256 KB
01_64_full.txt WA 1 ms 256 KB
01_65_min.txt WA 1 ms 256 KB
01_66_min.txt WA 1 ms 256 KB
01_67_min.txt WA 1 ms 256 KB
01_68_max.txt WA 1 ms 256 KB
01_69_max.txt WA 1 ms 256 KB
01_70_max.txt WA 1 ms 256 KB
01_71_max.txt WA 1 ms 256 KB
01_72_max.txt WA 1 ms 256 KB
02_100_min.txt WA 1 ms 256 KB
02_101_min.txt WA 1 ms 256 KB
02_102_max.txt WA 1 ms 256 KB
02_103_max.txt WA 1 ms 256 KB
02_104_max.txt WA 1 ms 256 KB
02_105_max.txt WA 1 ms 256 KB
02_106_max.txt WA 1 ms 256 KB
02_73_random.txt WA 1 ms 256 KB
02_74_random.txt WA 1 ms 256 KB
02_75_random.txt WA 1 ms 256 KB
02_76_random.txt WA 1 ms 256 KB
02_77_random.txt WA 1 ms 256 KB
02_78_random.txt WA 1 ms 256 KB
02_79_random.txt WA 1 ms 256 KB
02_80_random.txt WA 1 ms 256 KB
02_81_random.txt WA 1 ms 256 KB
02_82_random.txt WA 1 ms 256 KB
02_83_random.txt WA 1 ms 256 KB
02_84_random.txt WA 1 ms 256 KB
02_85_random.txt WA 1 ms 256 KB
02_86_random.txt WA 1 ms 256 KB
02_87_random.txt WA 1 ms 256 KB
02_88_random.txt WA 1 ms 256 KB
02_89_random.txt WA 1 ms 256 KB
02_90_random.txt WA 1 ms 256 KB
02_91_random.txt WA 1 ms 256 KB
02_92_random.txt WA 1 ms 256 KB
02_93_freedom.txt WA 1 ms 256 KB
02_94_freedom.txt WA 1 ms 256 KB
02_95_freedom.txt WA 1 ms 256 KB
02_96_full.txt WA 1 ms 256 KB
02_97_full.txt WA 1 ms 256 KB
02_98_full.txt WA 1 ms 256 KB
02_99_min.txt WA 1 ms 256 KB