oj.uz

Submission #198635

# Submission time Handle Problem Language Result Execution time Memory
198635 2020-01-27T05:45:16 Z arnold518 Cubeword (CEOI19_cubeword) C++14
21 / 100
 200 ms 21200 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int MAXS = 6;
const ll MOD = 998244353;

int N;
ll ans, cnt[70][70], D[70][70][70];
vector<string> S, T[15];

int convert(char s)
{
	if('a'<=s && s<='z') return s-'a';
	if('A'<=s && s<='Z') return s-'A'+26;
	if('0'<=s && s<='9') return s-'0'+52;
}

int main()
{
	int i, j, p, q, k;

	//ios_base::sync_with_stdio(false);
	//cin.tie(NULL); cout.tie(NULL);
	cin>>N;
	for(i=1; i<=N; i++)
	{
		string s, t;
		cin>>s; t=s;
		reverse(t.begin(), t.end());
		S.push_back(s);
		S.push_back(t);
	}

	sort(S.begin(), S.end());
	S.erase(unique(S.begin(), S.end()), S.end());

	for(i=0; i<S.size(); i++) T[S[i].size()].push_back(S[i]);

	for(k=3; k<=10; k++)
	{
		vector<string> V=T[k];
		if(V.empty()) continue;

		memset(cnt, 0, sizeof(cnt));
		memset(D, 0, sizeof(D));
		for(i=0; i<V.size(); i++) cnt[convert(V[i][0])][convert(V[i][V[i].size()-1])]++;

		for(i=0; i<MAXS; i++) for(j=0; j<MAXS; j++) for(p=0; p<MAXS; p++)
		{
			for(q=0; q<MAXS; q++)
			{
				D[i][j][p]+=cnt[i][q]*cnt[j][q]%MOD*cnt[p][q]%MOD;
				D[i][j][p]%=MOD;
			}
		}

		for(i=0; i<MAXS; i++) for(j=0; j<MAXS; j++) for(p=0; p<MAXS; p++) for(q=0; q<MAXS; q++)
		{
			ans+=D[i][j][p]*D[i][j][q]%MOD*D[i][p][q]%MOD*D[j][p][q]%MOD;
			ans%=MOD;
		}
	}
	cout<<ans;
}

Compilation message

cubeword.cpp: In function 'int main()':
cubeword.cpp:42:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<S.size(); i++) T[S[i].size()].push_back(S[i]);
           ~^~~~~~~~~
cubeword.cpp:51:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0; i<V.size(); i++) cnt[convert(V[i][0])][convert(V[i][V[i].size()-1])]++;
            ~^~~~~~~~~
cubeword.cpp: In function 'int convert(char)':
cubeword.cpp:21:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 19792 KB Output is correct
2 Correct 199 ms 19408 KB Output is correct
3 Correct 193 ms 20816 KB Output is correct
4 Correct 199 ms 21200 KB Output is correct
5 Correct 188 ms 20688 KB Output is correct
6 Correct 194 ms 20304 KB Output is correct
7 Correct 188 ms 20560 KB Output is correct
8 Correct 190 ms 20432 KB Output is correct
9 Correct 195 ms 21200 KB Output is correct
10 Correct 200 ms 20688 KB Output is correct
11 Correct 191 ms 20304 KB Output is correct
12 Correct 192 ms 20176 KB Output is correct
13 Correct 189 ms 19792 KB Output is correct
14 Correct 195 ms 20944 KB Output is correct
15 Correct 192 ms 20308 KB Output is correct
16 Correct 191 ms 20948 KB Output is correct
17 Correct 189 ms 20176 KB Output is correct
18 Correct 190 ms 20308 KB Output is correct
19 Correct 186 ms 19664 KB Output is correct
20 Correct 189 ms 21072 KB Output is correct
21 Correct 192 ms 20176 KB Output is correct

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 19792 KB Output is correct
2 Correct 199 ms 19408 KB Output is correct
3 Correct 193 ms 20816 KB Output is correct
4 Correct 199 ms 21200 KB Output is correct
5 Correct 188 ms 20688 KB Output is correct
6 Correct 194 ms 20304 KB Output is correct
7 Correct 188 ms 20560 KB Output is correct
8 Correct 190 ms 20432 KB Output is correct
9 Correct 195 ms 21200 KB Output is correct
10 Correct 200 ms 20688 KB Output is correct
11 Correct 191 ms 20304 KB Output is correct
12 Correct 192 ms 20176 KB Output is correct
13 Correct 189 ms 19792 KB Output is correct
14 Correct 195 ms 20944 KB Output is correct
15 Correct 192 ms 20308 KB Output is correct
16 Correct 191 ms 20948 KB Output is correct
17 Correct 189 ms 20176 KB Output is correct
18 Correct 190 ms 20308 KB Output is correct
19 Correct 186 ms 19664 KB Output is correct
20 Correct 189 ms 21072 KB Output is correct
21 Correct 192 ms 20176 KB Output is correct
22 Incorrect 187 ms 17744 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 19792 KB Output is correct
2 Correct 199 ms 19408 KB Output is correct
3 Correct 193 ms 20816 KB Output is correct
4 Correct 199 ms 21200 KB Output is correct
5 Correct 188 ms 20688 KB Output is correct
6 Correct 194 ms 20304 KB Output is correct
7 Correct 188 ms 20560 KB Output is correct
8 Correct 190 ms 20432 KB Output is correct
9 Correct 195 ms 21200 KB Output is correct
10 Correct 200 ms 20688 KB Output is correct
11 Correct 191 ms 20304 KB Output is correct
12 Correct 192 ms 20176 KB Output is correct
13 Correct 189 ms 19792 KB Output is correct
14 Correct 195 ms 20944 KB Output is correct
15 Correct 192 ms 20308 KB Output is correct
16 Correct 191 ms 20948 KB Output is correct
17 Correct 189 ms 20176 KB Output is correct
18 Correct 190 ms 20308 KB Output is correct
19 Correct 186 ms 19664 KB Output is correct
20 Correct 189 ms 21072 KB Output is correct
21 Correct 192 ms 20176 KB Output is correct
22 Incorrect 187 ms 17744 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 19792 KB Output is correct
2 Correct 199 ms 19408 KB Output is correct
3 Correct 193 ms 20816 KB Output is correct
4 Correct 199 ms 21200 KB Output is correct
5 Correct 188 ms 20688 KB Output is correct
6 Correct 194 ms 20304 KB Output is correct
7 Correct 188 ms 20560 KB Output is correct
8 Correct 190 ms 20432 KB Output is correct
9 Correct 195 ms 21200 KB Output is correct
10 Correct 200 ms 20688 KB Output is correct
11 Correct 191 ms 20304 KB Output is correct
12 Correct 192 ms 20176 KB Output is correct
13 Correct 189 ms 19792 KB Output is correct
14 Correct 195 ms 20944 KB Output is correct
15 Correct 192 ms 20308 KB Output is correct
16 Correct 191 ms 20948 KB Output is correct
17 Correct 189 ms 20176 KB Output is correct
18 Correct 190 ms 20308 KB Output is correct
19 Correct 186 ms 19664 KB Output is correct
20 Correct 189 ms 21072 KB Output is correct
21 Correct 192 ms 20176 KB Output is correct
22 Incorrect 187 ms 17744 KB Output isn't correct
23 Halted 0 ms 0 KB -