oj.uz

Submission #733117

# Submission time Handle Problem Language Result Execution time Memory
733117 2023-04-30T06:24:15 Z vjudge1 Trener (COCI20_trener) C++17
110 / 110
 91 ms 2512 KB 
#include<bits/stdc++.h>
#define int long long
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

const int p2=37;

int p[1505];

int add(int x,int y){
	return ((x+y)%MOD+MOD)%MOD;
}

int mul(int x,int y){
	return (x*y)%MOD;
}

int fp(int a,int b){
	if(b==0)return 1;
	int t=fp(a,b/2);
	t=(t*t)%MOD;
	if(b%2)return (t*a)%MOD;
	return t;
}
int32_t main(){
	srand(time(NULL));
	fast;
	p[0]=1;
	for(int i=1;i<=1500;i++)p[i]=mul(p[i-1],p2);
	int n,m;
	cin>>n>>m;
	map<int,int>mp;
	for(int i=0;i<n;i++){
		map<int,int>mp2;
		for(int j=0;j<m;j++){
			string s;
			cin>>s;
			int a=0;
			for(int k=0;k<s.size()-1;k++){
				a=add(a,mul(s[k]-'a'+1,p[k]));
			}
			int b;
			if(i!=0)b=add(mul(s.back()-'a'+1,p[i-1]),mul(fp(p2,MOD-2),add(a,-(s[0]-'a'+1))));
			int c=add(a,mul(s.back()-'a'+1,p[i]));
			if(i==0){
				mp2[c]++;
				mp2[c]%=MOD;
				continue;
			}
			mp2[c]=add(mp2[c],add(mp[a],mp[b]));
			if(a==b){
				mp2[c]=add(mp2[c],-mp[a]);
			}
		}
		mp.clear();
		mp=mp2;
	}
	int ans=0;
	for(auto i:mp)ans=add(ans,i.ss);
	cout<<ans<<endl;
}

Compilation message

trener.cpp: In function 'int32_t main()':
trener.cpp:45:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |    for(int k=0;k<s.size()-1;k++){
      |                ~^~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 216 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Output is correct
2 Correct 5 ms 460 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 4 ms 464 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 216 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 5 ms 460 KB Output is correct
7 Correct 5 ms 468 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 5 ms 468 KB Output is correct
11 Correct 4 ms 464 KB Output is correct
12 Correct 84 ms 2512 KB Output is correct
13 Correct 78 ms 2496 KB Output is correct
14 Correct 84 ms 2508 KB Output is correct
15 Correct 91 ms 2496 KB Output is correct
16 Correct 39 ms 2252 KB Output is correct
17 Correct 67 ms 2440 KB Output is correct
18 Correct 72 ms 2444 KB Output is correct
19 Correct 67 ms 2452 KB Output is correct
20 Correct 69 ms 2440 KB Output is correct
21 Correct 67 ms 2388 KB Output is correct
22 Correct 43 ms 2252 KB Output is correct