Submission #223582

#	Time	Username	Problem	Language	Result	Execution time	Memory
223582		CaroLinda	Cubeword (CEOI19_cubeword)	C++14	100 / 100	578 ms	26248 KiB

cubeword

#include <bits/stdc++.h>

#define all(x) x.begin(),x.end()
#define lp(i,a,b) for(int i = a ; i < b ; i++)
#define pii pair<int,int>
#define pb push_back
#define mk make_pair
#define ll long long
#define ff first
#define ss second
#define debug printf

const int MAXN = 1e5+10 ;
const int MAX = 64 ;
const int MOD =  998244353 ;

using namespace std ;

int N ;
ll resp ;
ll dp[MAX][MAX][MAX] ;
ll fat[10] ;
string aux ;
vector<string> str[ 15 ] ;
int code[200] ;
int mat[MAX][MAX] ;
set<string> S ;

ll perm(int a , int b, int c, int d)
{

    int s[4] = {a,b,c,d} ;

    ll tot = 24LL ;

    int last = 0 ;

    for(int i = 1 ; i < 4 ; i++ )
    {
        if( s[i] == s[i-1] ) continue ;
        tot /= fat[( i - last )] ;
        last = i ;
    }

    tot /= fat[(4-last)] ;

    return tot ;

}

inline void calculate( vector<string> v )
{

    lp(i,0,62)
        lp(j,0,62) mat[i][j] = 0 ;

    for(auto s : v )
    {
        int x = code[s[0]] ;
        int y = code[ s[ s.size()-1 ] ] ;

        mat[x][y] ++ ;
    }

    for(int i = 0 ; i < 62 ; i++ )
        for(int j = i ; j < 62 ; j++ )
            for(int g = j ; g < 62 ; g++ )
            {
                dp[i][j][g] = 0LL ;

                for(int k = 0 ; k < 62 ; k++ )
                {
                    ll to_add = ( 1LL*mat[i][k] * mat[j][k] ) % MOD ;
                    to_add *= 1LL*mat[g][k] ;
                    to_add %= MOD ;

                    dp[i][j][g] += to_add ;
                    dp[i][j][g] %= MOD ;

                }

                dp[i][g][j] = dp[j][i][g] = dp[j][g][i] = dp[g][i][j] = dp[g][j][i] = dp[i][j][g] ;

            }

    for(int a = 0 ;a < 62 ; a  ++ )
        for(int b = a ; b < 62 ; b++ )
            for(int c = b ; c < 62 ; c++ )
                for(int d = c ; d < 62 ; d++ )
                {
                    ll to_add = 1LL*dp[a][b][c]*dp[a][b][d] ;
                    to_add %= MOD ;

                    to_add *= (1LL*dp[b][c][d]*dp[a][c][d])%MOD ;
                    to_add %= MOD ;

                    to_add *= perm(a,b,c,d) ;
                    to_add %= MOD ;

                    resp += to_add ;
                    resp %= MOD ;

                }

}

int main()
{

    lp(i,0,26) code[ i + 'A' ] = i ;
    lp(i,0,26) code[ i + 'a' ] = i+26 ;
    lp(i,0,10) code[i+'0'] = i + 52 ;
    fat[0] = 1 ;
    for(int i = 1 ; i < 10 ; i++ ) fat[i] = i*fat[i-1] ;

    scanf("%d", &N ) ;
    for(int i = 1 , tam , x , y ;i <= N ; i++ )
    {
        cin >> aux ;
        S.insert(aux) ;
        reverse(all(aux)) ;
        S.insert(aux) ;
    }

    for(auto s : S) str[ s.size() ].pb(s) ;

    lp(i,3,11) calculate( str[i]) ;

    printf("%lld\n" , resp ) ;

}

Compilation message (stderr)

cubeword.cpp: In function 'void calculate(std::vector<std::__cxx11::basic_string<char> >)':
cubeword.cpp:59:26: warning: array subscript has type 'char' [-Wchar-subscripts]
         int x = code[s[0]] ;
                          ^
cubeword.cpp:60:39: warning: array subscript has type 'char' [-Wchar-subscripts]
         int y = code[ s[ s.size()-1 ] ] ;
                                       ^
cubeword.cpp: In function 'int main()':
cubeword.cpp:117:21: warning: unused variable 'tam' [-Wunused-variable]
     for(int i = 1 , tam , x , y ;i <= N ; i++ )
                     ^~~
cubeword.cpp:117:27: warning: unused variable 'x' [-Wunused-variable]
     for(int i = 1 , tam , x , y ;i <= N ; i++ )
                           ^
cubeword.cpp:117:31: warning: unused variable 'y' [-Wunused-variable]
     for(int i = 1 , tam , x , y ;i <= N ; i++ )
                               ^
cubeword.cpp:116:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N ) ;
     ~~~~~^~~~~~~~~~~

• Subtask 1: 21 / 21
• Subtask 2: 29 / 29
• Subtask 3: 34 / 34
• Subtask 4: 16 / 16