oj.uz

Submission #223205

# Submission time Handle Problem Language Result Execution time Memory
223205 2020-04-15T05:07:53 Z oolimry Trener (COCI20_trener) C++14
22 / 110
 86 ms 2168 KB 
#include <bits/stdc++.h>

using namespace std;
long long mod = 1000000007;

inline long long add(long long a, long long b){
	a += b;
	if(a >= mod) a -= mod;
	return a;
}


unordered_map<string, long long> m;
unordered_map<string, long long> mm;

void prop(string s, long long x){
	//cout << s << " " << x << "\n";
	if(x == 0) return;
	for(char c = 'a';c <= 'z';c++){
		//cout << s+c << " " << c+s << "\n";
		mm[s+c] += x;
		if(s + c != c + s) mm[c+s] += x;
		while(mm[c+s] >= mod) mm[c+s] -= mod;
	}
}

int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, k; cin >> n >> k;
	
	if(n == 1){
		cout << k;
		return 0;
	}
	
	for(int j = 0;j < k;j++){
		string s; cin >> s;
		prop(s, 1);
	}
	

	
	for(int i = 2;i <= n-1;i++){
		swap(m, mm);
		mm.clear();
		for(int j = 0;j < k;j++){
			string s; cin >> s;
			prop(s, m[s]);
		}
	}
	
	long long ans = 0;
	for(int j = 0;j < k;j++){
		string s; cin >> s;
		ans = add(ans, mm[s]);
	}
	
	cout << ans;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 1784 KB Output is correct
2 Correct 72 ms 2168 KB Output is correct
3 Correct 73 ms 2040 KB Output is correct
4 Correct 74 ms 384 KB Output is correct
5 Incorrect 86 ms 1784 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 74 ms 1784 KB Output is correct
6 Correct 72 ms 2168 KB Output is correct
7 Correct 73 ms 2040 KB Output is correct
8 Correct 74 ms 384 KB Output is correct
9 Incorrect 86 ms 1784 KB Output isn't correct
10 Halted 0 ms 0 KB -