제출 #1078725

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1078725		khactrung1912	Lozinke (COCI17_lozinke)	C++14	40 / 100	1075 ms	13916 KiB

lozinke

#include <bits/stdc++.h>
#define quick ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define file(name) freopen(name".inp","r",stdin); freopen(name".out","w",stdout);
#define endl '\n'
#define N 100000
#define pii pair <int,int>
using namespace std;
const int INF = 1e9;
const int base=1001;
const int mod=1e10+7;
const int MOD=1e10+3;
vector <long long> sum[N],SUM[N];
vector <long long> h,H;
int n;
string st[N];
long long get(int u,int v, vector <long long> &s,vector <long long> hh,long long mo)
{
	long long mm=mo*mo;
	return (s[v]-s[u-1]*h[v-u+1]+mm)%mo;
}
bool cmp(string a,string b)
{
    return a.size()<b.size();
}
int main()
{
	quick;
	//file("pass");
	cin>>n;
    for (int i=1;i<=n;i++) cin>>st[i];
    sort(st+1,st+n+1,cmp);
	for (int i=1;i<=n;i++)
	{
		string s;
		s=st[i];
		int m=s.size();
		s=' '+s;
		sum[i].push_back(0);
		SUM[i].push_back(0);
		for (int j=1;j<=m;j++) sum[i].push_back((sum[i][j-1]*base+s[j])%mod);
		for (int j=1;j<=m;j++) SUM[i].push_back((SUM[i][j-1]*base+s[j])%MOD);
	}
	h.push_back(1);
    H.push_back(1);
	for (int i=1;i<=100;i++) h.push_back(h[i-1]*base%mod);
    for (int i=1;i<=100;i++) H.push_back(H[i-1]*base%mod);
    long long ans=0;
    for (int i=1;i<n;i++)
    {
        long long a=get(1,st[i].size(),sum[i],h,mod),b=get(1,st[i].size(),SUM[i],H,MOD);
//        cout<<a<<' '<<b<<endl;
        for (int j=i+1;j<=n;j++) 
            for (int k=1;k<=st[j].size()-st[i].size()+1;k++)
        {
//        	    cout<<j<<' '<<get(k,k+st[i].size()-1,sum[j],h,mod)<<' '<<get(k,k+st[i].size()-1,SUM[j],H,MOD)<<endl;
                if (a==get(k,k+st[i].size()-1,sum[j],h,mod) && b==get(k,k+st[i].size()-1,SUM[j],H,MOD))
                {
                    ans++;
                    if (st[i]==st[j]) ans++;
                    break;
                }
                
        }
    }
    cout<<ans;
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

lozinke.cpp:10:19: warning: overflow in conversion from 'double' to 'int' changes value from '1.0000000007e+10' to '2147483647' [-Woverflow]
   10 | const int mod=1e10+7;
      |               ~~~~^~
lozinke.cpp:11:19: warning: overflow in conversion from 'double' to 'int' changes value from '1.0000000003e+10' to '2147483647' [-Woverflow]
   11 | const int MOD=1e10+3;
      |               ~~~~^~
lozinke.cpp: In function 'int main()':
lozinke.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             for (int k=1;k<=st[j].size()-st[i].size()+1;k++)
      |                          ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 40 / 100