oj.uz

Submission #210852

# Submission time Handle Problem Language Result Execution time Memory
210852 2020-03-18T21:37:44 Z Lawliet Cubeword (CEOI19_cubeword) C++17
84 / 100
 667 ms 32888 KB 
#include <bits/stdc++.h>
 
using namespace std;
typedef long long int lli;
 
const int MAXS = 10;
const int MAXL = 35;
const int MAXN = 100010;
const int MOD = 998244353;
 
int n;
 
int qtd[MAXL][MAXL][MAXS];
 
lli ans[MAXL][MAXL][MAXL][MAXS];
 
lli result;
 
vector< int > p;
 
set< string > s;
 
int conv(char a)
{
	if( 'a' <= a && a <= 'p' ) return a - 'a';
	return 'p' - 'a' + 1 + a - 'A';
}
 
void backtracking(int i)
{
	if( i == 4 )
	{
		for(int sz = 3 ; sz <= 10 ; sz++)
		{
			lli t = 1;
 
			t *= ans[ p[0] ][ p[1] ][ p[2] ][sz];
			t *= ans[ p[0] ][ p[1] ][ p[3] ][sz]; t %= MOD;
			t *= ans[ p[0] ][ p[2] ][ p[3] ][sz]; t %= MOD;
			t *= ans[ p[1] ][ p[2] ][ p[3] ][sz]; t %= MOD;
 
			result += t;
			result %= MOD;
		}
 
		return;
	}
 
	for(int k = 0 ; k <= conv( 'P' ) ; k++)
	{
		p.push_back( k );
		backtracking( i + 1 );
		p.pop_back();
	}
}
 
int main()
{
	cin >> n;
 
	for(int i = 1 ; i <= n ; i++)
	{
		string t;
		cin >> t;
 
		s.insert( t );
		reverse( t.begin() , t.end() );
		s.insert( t );
	}
 
	for(auto it = s.begin() ; it != s.end() ; it++)
	{
		string curT = *it;
 
		int first = conv( curT[0] );
		int last = conv( curT.back() );
		int sz = curT.size();
 
		qtd[first][last][sz]++;
	}
 
	for(int a = 0 ; a <= conv( 'P' ) ; a++)
	{
		for(int b = 0 ; b <= conv( 'P' ) ; b++)
		{
			for(int c = 0 ; c <= conv( 'P' ) ; c++)
			{
				for(int sz = 3 ; sz <= 10 ; sz++)
				{
					for(int k = 0 ; k <= conv( 'P' ) ; k++)
					{
						lli aux = 1;
 
						aux *= qtd[a][k][sz];
						aux *= qtd[b][k][sz];
						aux *= qtd[c][k][sz];
 
						ans[a][b][c][sz] += aux;
						ans[a][b][c][sz] %= MOD;
					}
				}
			}
		}
	}
 
	backtracking( 0 );
 
	printf("%lld\n",result);
}

Compilation message

cubeword.cpp: In function 'void backtracking(int)':
cubeword.cpp:37:6: warning: iteration 7 invokes undefined behavior [-Waggressive-loop-optimizations]
    t *= ans[ p[0] ][ p[1] ][ p[2] ][sz];
    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cubeword.cpp:33:23: note: within this loop
   for(int sz = 3 ; sz <= 10 ; sz++)
                    ~~~^~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 18756 KB Output is correct
2 Correct 528 ms 18600 KB Output is correct
3 Correct 513 ms 18680 KB Output is correct
4 Correct 501 ms 18656 KB Output is correct
5 Correct 541 ms 18580 KB Output is correct
6 Correct 514 ms 18680 KB Output is correct
7 Correct 551 ms 18764 KB Output is correct
8 Correct 550 ms 18572 KB Output is correct
9 Correct 564 ms 18720 KB Output is correct
10 Correct 589 ms 18736 KB Output is correct
11 Correct 667 ms 18792 KB Output is correct
12 Correct 629 ms 18680 KB Output is correct
13 Correct 551 ms 18820 KB Output is correct
14 Correct 533 ms 18568 KB Output is correct
15 Correct 587 ms 18604 KB Output is correct
16 Correct 603 ms 18632 KB Output is correct
17 Correct 524 ms 18680 KB Output is correct
18 Correct 558 ms 18772 KB Output is correct
19 Correct 513 ms 18808 KB Output is correct
20 Correct 491 ms 18952 KB Output is correct
21 Correct 552 ms 18668 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 18756 KB Output is correct
2 Correct 528 ms 18600 KB Output is correct
3 Correct 513 ms 18680 KB Output is correct
4 Correct 501 ms 18656 KB Output is correct
5 Correct 541 ms 18580 KB Output is correct
6 Correct 514 ms 18680 KB Output is correct
7 Correct 551 ms 18764 KB Output is correct
8 Correct 550 ms 18572 KB Output is correct
9 Correct 564 ms 18720 KB Output is correct
10 Correct 589 ms 18736 KB Output is correct
11 Correct 667 ms 18792 KB Output is correct
12 Correct 629 ms 18680 KB Output is correct
13 Correct 551 ms 18820 KB Output is correct
14 Correct 533 ms 18568 KB Output is correct
15 Correct 587 ms 18604 KB Output is correct
16 Correct 603 ms 18632 KB Output is correct
17 Correct 524 ms 18680 KB Output is correct
18 Correct 558 ms 18772 KB Output is correct
19 Correct 513 ms 18808 KB Output is correct
20 Correct 491 ms 18952 KB Output is correct
21 Correct 552 ms 18668 KB Output is correct
22 Correct 511 ms 19308 KB Output is correct
23 Correct 522 ms 19244 KB Output is correct
24 Correct 517 ms 19488 KB Output is correct
25 Correct 528 ms 19448 KB Output is correct
26 Correct 567 ms 19352 KB Output is correct
27 Correct 538 ms 19240 KB Output is correct
28 Correct 548 ms 19220 KB Output is correct
29 Correct 560 ms 19548 KB Output is correct
30 Correct 543 ms 19476 KB Output is correct
31 Correct 562 ms 19388 KB Output is correct
32 Correct 543 ms 19324 KB Output is correct
33 Correct 522 ms 19376 KB Output is correct
34 Correct 516 ms 19248 KB Output is correct
35 Correct 596 ms 19264 KB Output is correct
36 Correct 630 ms 19280 KB Output is correct
37 Correct 622 ms 19420 KB Output is correct
38 Correct 580 ms 19232 KB Output is correct
39 Correct 574 ms 19208 KB Output is correct
40 Correct 565 ms 19172 KB Output is correct
41 Correct 583 ms 19276 KB Output is correct
42 Correct 591 ms 19248 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 18756 KB Output is correct
2 Correct 528 ms 18600 KB Output is correct
3 Correct 513 ms 18680 KB Output is correct
4 Correct 501 ms 18656 KB Output is correct
5 Correct 541 ms 18580 KB Output is correct
6 Correct 514 ms 18680 KB Output is correct
7 Correct 551 ms 18764 KB Output is correct
8 Correct 550 ms 18572 KB Output is correct
9 Correct 564 ms 18720 KB Output is correct
10 Correct 589 ms 18736 KB Output is correct
11 Correct 667 ms 18792 KB Output is correct
12 Correct 629 ms 18680 KB Output is correct
13 Correct 551 ms 18820 KB Output is correct
14 Correct 533 ms 18568 KB Output is correct
15 Correct 587 ms 18604 KB Output is correct
16 Correct 603 ms 18632 KB Output is correct
17 Correct 524 ms 18680 KB Output is correct
18 Correct 558 ms 18772 KB Output is correct
19 Correct 513 ms 18808 KB Output is correct
20 Correct 491 ms 18952 KB Output is correct
21 Correct 552 ms 18668 KB Output is correct
22 Correct 511 ms 19308 KB Output is correct
23 Correct 522 ms 19244 KB Output is correct
24 Correct 517 ms 19488 KB Output is correct
25 Correct 528 ms 19448 KB Output is correct
26 Correct 567 ms 19352 KB Output is correct
27 Correct 538 ms 19240 KB Output is correct
28 Correct 548 ms 19220 KB Output is correct
29 Correct 560 ms 19548 KB Output is correct
30 Correct 543 ms 19476 KB Output is correct
31 Correct 562 ms 19388 KB Output is correct
32 Correct 543 ms 19324 KB Output is correct
33 Correct 522 ms 19376 KB Output is correct
34 Correct 516 ms 19248 KB Output is correct
35 Correct 596 ms 19264 KB Output is correct
36 Correct 630 ms 19280 KB Output is correct
37 Correct 622 ms 19420 KB Output is correct
38 Correct 580 ms 19232 KB Output is correct
39 Correct 574 ms 19208 KB Output is correct
40 Correct 565 ms 19172 KB Output is correct
41 Correct 583 ms 19276 KB Output is correct
42 Correct 591 ms 19248 KB Output is correct
43 Correct 569 ms 19476 KB Output is correct
44 Correct 593 ms 19476 KB Output is correct
45 Correct 604 ms 19484 KB Output is correct
46 Correct 586 ms 19460 KB Output is correct
47 Correct 611 ms 19464 KB Output is correct
48 Correct 581 ms 19528 KB Output is correct
49 Correct 574 ms 19456 KB Output is correct
50 Correct 565 ms 19436 KB Output is correct
51 Correct 575 ms 19460 KB Output is correct
52 Correct 568 ms 19452 KB Output is correct
53 Correct 557 ms 19476 KB Output is correct
54 Correct 547 ms 19432 KB Output is correct
55 Correct 589 ms 19412 KB Output is correct
56 Correct 557 ms 19448 KB Output is correct
57 Correct 565 ms 19444 KB Output is correct
58 Correct 543 ms 19448 KB Output is correct
59 Correct 563 ms 19604 KB Output is correct
60 Correct 582 ms 19408 KB Output is correct
61 Correct 584 ms 19416 KB Output is correct
62 Correct 584 ms 19556 KB Output is correct
63 Correct 555 ms 19336 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 18756 KB Output is correct
2 Correct 528 ms 18600 KB Output is correct
3 Correct 513 ms 18680 KB Output is correct
4 Correct 501 ms 18656 KB Output is correct
5 Correct 541 ms 18580 KB Output is correct
6 Correct 514 ms 18680 KB Output is correct
7 Correct 551 ms 18764 KB Output is correct
8 Correct 550 ms 18572 KB Output is correct
9 Correct 564 ms 18720 KB Output is correct
10 Correct 589 ms 18736 KB Output is correct
11 Correct 667 ms 18792 KB Output is correct
12 Correct 629 ms 18680 KB Output is correct
13 Correct 551 ms 18820 KB Output is correct
14 Correct 533 ms 18568 KB Output is correct
15 Correct 587 ms 18604 KB Output is correct
16 Correct 603 ms 18632 KB Output is correct
17 Correct 524 ms 18680 KB Output is correct
18 Correct 558 ms 18772 KB Output is correct
19 Correct 513 ms 18808 KB Output is correct
20 Correct 491 ms 18952 KB Output is correct
21 Correct 552 ms 18668 KB Output is correct
22 Correct 511 ms 19308 KB Output is correct
23 Correct 522 ms 19244 KB Output is correct
24 Correct 517 ms 19488 KB Output is correct
25 Correct 528 ms 19448 KB Output is correct
26 Correct 567 ms 19352 KB Output is correct
27 Correct 538 ms 19240 KB Output is correct
28 Correct 548 ms 19220 KB Output is correct
29 Correct 560 ms 19548 KB Output is correct
30 Correct 543 ms 19476 KB Output is correct
31 Correct 562 ms 19388 KB Output is correct
32 Correct 543 ms 19324 KB Output is correct
33 Correct 522 ms 19376 KB Output is correct
34 Correct 516 ms 19248 KB Output is correct
35 Correct 596 ms 19264 KB Output is correct
36 Correct 630 ms 19280 KB Output is correct
37 Correct 622 ms 19420 KB Output is correct
38 Correct 580 ms 19232 KB Output is correct
39 Correct 574 ms 19208 KB Output is correct
40 Correct 565 ms 19172 KB Output is correct
41 Correct 583 ms 19276 KB Output is correct
42 Correct 591 ms 19248 KB Output is correct
43 Correct 569 ms 19476 KB Output is correct
44 Correct 593 ms 19476 KB Output is correct
45 Correct 604 ms 19484 KB Output is correct
46 Correct 586 ms 19460 KB Output is correct
47 Correct 611 ms 19464 KB Output is correct
48 Correct 581 ms 19528 KB Output is correct
49 Correct 574 ms 19456 KB Output is correct
50 Correct 565 ms 19436 KB Output is correct
51 Correct 575 ms 19460 KB Output is correct
52 Correct 568 ms 19452 KB Output is correct
53 Correct 557 ms 19476 KB Output is correct
54 Correct 547 ms 19432 KB Output is correct
55 Correct 589 ms 19412 KB Output is correct
56 Correct 557 ms 19448 KB Output is correct
57 Correct 565 ms 19444 KB Output is correct
58 Correct 543 ms 19448 KB Output is correct
59 Correct 563 ms 19604 KB Output is correct
60 Correct 582 ms 19408 KB Output is correct
61 Correct 584 ms 19416 KB Output is correct
62 Correct 584 ms 19556 KB Output is correct
63 Correct 555 ms 19336 KB Output is correct
64 Runtime error 397 ms 32888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
65 Halted 0 ms 0 KB -