oj.uz

Submission #845571

# Submission time Handle Problem Language Result Execution time Memory
845571 2023-09-06T14:12:13 Z vjudge1 Trener (COCI20_trener) C++17
0 / 110
 12 ms 344 KB 
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
#define N 200005
using namespace std;
const int hbase = 127, hmod = 1610612741, ansmod = 1000000007;

int binpow(int x, int y, const int modulo) {
	int ret = 1;
	while(y) {
		if(y & 1) {
			ret *= x;
			ret %= modulo;
		}
		y /= 2;
		x *= x;
		x %= modulo;
	}
	return ret;
}

int hashing(string s) {
	// cout<<s<<"\n";
	int ret = 0;
	for(int i = 0; i < s.size(); i++) {
		ret += binpow(hbase, i, hmod) * (s[i] - 97);
		ret %= hmod;
	}
	// cout<<ret<<"\n";
	return ret;
}

int32_t main(){
	fast
	int n, k;
	cin>>n>>k;
	vector<string> ss(k);
	map <int, int> dp; // öncekilerin hashleri ile dpleri
	for(int i = 0; i < n; i++) {
		map <int, int> tdp;
		for(int j = 0; j < k; j++) {
			cin>>ss[j];
			tdp.insert( { hashing(ss[j]), 0ll } );
		}


		if(!i) { // i 0 ise
			for(auto& it:tdp) {
				it.second = 1;
			}
			for(auto it:tdp) {
				dp.insert(it);
			}
			continue;
		}

		for(auto it:dp) {
		}

		for(int j = 0; j < k; j++) {
			int val = 0;

			string temp = ss[j];
			temp.erase(temp.begin());
			if( dp.count(hashing(temp)) ) val += dp[hashing(temp)];

			string temp2 = ss[j];
			temp2.pop_back();
			if( temp != temp2 and dp.count(hashing(temp2)) ) val += dp[hashing(temp2)];

			tdp[hashing(ss[j])] = (val + tdp[hashing(ss[j])]) % ansmod;
		}

		dp.clear();
		for(auto it:tdp) {
			dp.insert(it);
		}
	}
	int ans = 0;
	for(auto it:dp) {
		ans = (ans + it.second) % ansmod;
	}
	cout<<ans<<"\n";
}

Compilation message

trener.cpp: In function 'long long int hashing(std::string)':
trener.cpp:26:19: 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]
   26 |  for(int i = 0; i < s.size(); i++) {
      |                 ~~^~~~~~~~~~
trener.cpp: In function 'int32_t main()':
trener.cpp:58:12: warning: variable 'it' set but not used [-Wunused-but-set-variable]
   58 |   for(auto it:dp) {
      |            ^~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -