Submission #1293262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293262		HoriaHaivas	Cubeword (CEOI19_cubeword)	C++20	100 / 100	897 ms	21540 KiB

cubeword

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

const int lim=62;///ar trebui sa fie 62 cred
const int mod=998244353;
int compatibil[70][70][70];
int cuvinte[70][70];
map<string,bool> seen;
string s[100005];

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

bool palindrome(string s)
{
    string s2;
    s2=s;
    reverse(s2.begin(),s2.end());
    return (s2==s);
}

signed main()
{
    /*
    ifstream fin("arbore.in");
    ofstream fout("arbore.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,i,j,k,l,r,x,ans,len,bigans,doit;
    cin >> n;
    for (i=1; i<=n; i++)
    {
        cin >> s[i];
    }
    bigans=0;
    for (len=3; len<=10; len++)
    {
        doit=0;
        for (i=1; i<=n; i++)
        {
            if (s[i].size()==len)
            {
                doit=1;
                l=convert(s[i][0]);
                r=convert(s[i].back());
                if (!seen[s[i]])
                {
                    cuvinte[l][r]++;
                    seen[s[i]]=1;
                }
                reverse(s[i].begin(),s[i].end());
                if (!seen[s[i]])
                {
                    cuvinte[r][l]++;
                    seen[s[i]]=1;
                }
            }
        }
        if (doit)
        {
            for (i=1; i<=lim; i++)
            {
                for (j=1; j<=lim; j++)
                {
                    for (k=1; k<=lim; k++)
                    {
                        ans=0;
                        for (x=1; x<=lim; x++)
                        {
                            ans+=(((cuvinte[i][x]*cuvinte[x][j])%mod)*cuvinte[x][k])%mod;
                            if (ans>=mod)
                                ans-=mod;
                        }
                        compatibil[i][j][k]=ans;
                    }
                }
            }
            for (i=1; i<=lim; i++) ///jos 1
            {
                for (j=1; j<=lim; j++) ///jos 2
                {
                    for (k=1; k<=lim; k++) ///sus 1
                    {
                        for (x=1; x<=lim; x++) ///sus 2
                        {
                            ans=(compatibil[j][k][x]*compatibil[i][k][x])%mod;
                            ans=(ans*((compatibil[x][i][j]*compatibil[k][i][j])%mod))%mod;
                            bigans+=ans;
                            if (bigans>=mod)
                                bigans-=mod;
                        }
                    }
                }
            }
        }
        for (i=1;i<=lim;i++)
        {
             for (j=1;j<=lim;j++)
                  cuvinte[i][j]=0;
        }
    }
    cout << bigans;
    ///vezi cum trebuie sa faci pentru palindroame etc
    return 0;
}

Compilation message (stderr)

cubeword.cpp: In function 'long long int convert(char)':
cubeword.cpp:31:1: warning: control reaches end of non-void function [-Wreturn-type]
   31 | }
      | ^

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