Submission #466717

#	Time	Username	Problem	Language	Result	Execution time	Memory
466717		ivan_tudor	Cubeword (CEOI19_cubeword)	C++14	100 / 100	289 ms	8816 KiB

cubeword

#include<bits/stdc++.h>
using namespace std;
vector<string> v[11];
const int MOD = 998244353;
void add(int &x, long long y){
  y%=MOD;
  x+=y;
  if(x>=MOD)
    x-=MOD;
  if(x<0)
    x+=MOD;
}
int codes(char c){
  if(c >= 'a' && c <= 'z')
    return c - 'a';
  else if( c >= 'A' && c<= 'Z')
    return c - 'A' + 'z' - 'a' + 1;
  else if(c >= '0' && c <= '9'){
    return c - '0' + 'Z' - 'A' + 1 + 'z' - 'a' + 1;
  }
  assert(0);
  return -1;
}
const int SIGMA = 'Z' - 'A' + 1 + 'z' - 'a' + 1 + '9' - '0' + 1 + 1;
int nw[SIGMA][SIGMA];
int nr[SIGMA][SIGMA][SIGMA];
int coef(int l1, int l2, int l3, int l4){
  if(l1 == l4)
    return 1;
  if(l1 == l3 || l2 == l4)
    return 4;
  if(l1 == l2 && l3 == l4)
    return 6;
  if(l1 == l2 || l2 == l3 || l3 == l4)
    return 12;
  return 24;
}
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n;
  cin>>n;
  for(int i = 1; i <=n; i++){
    string s;
    cin>>s;
    int len = s.size();
    v[len].push_back(s);
    reverse(s.begin(), s.end());
    v[len].push_back(s);
  }
  int ans = 0;
  for(int len = 3; len<=10; len++){
    // doar ce e unic
    sort(v[len].begin(), v[len].end());
    auto last = unique(v[len].begin(), v[len].end());
    v[len].erase(last, v[len].end());
    for(string x:v[len]){
      nw[codes(x[0])][codes(x[x.size() - 1])]++;
    }
    for(int l1 = 0; l1 < SIGMA; l1++){
      for(int l2 = l1; l2 < SIGMA; l2++){
        for(int l3 = l2; l3 < SIGMA; l3++){
          for(int l4 = 0; l4 < SIGMA; l4++){
            long long ad = 1LL * nw[l4][l1] * nw[l4][l2] % MOD * nw[l4][l3] % MOD;
            if(add)
              add(nr[l1][l2][l3], ad);
          }
        }
      }
    }
    for(int l1 = 0; l1 < SIGMA; l1++){
      for(int l2 = l1; l2 < SIGMA; l2++){
        for(int l3 = l2; l3 < SIGMA; l3++){
          for(int l4 = l3; l4 < SIGMA; l4++){
            long long nwc = 1LL *nr[l1][l2][l3] * nr[l1][l2][l4] % MOD * nr[l1][l3][l4] % MOD * nr[l2][l3][l4] % MOD;
            if(nwc)
              add(ans, 1LL *nwc * coef(l1, l2, l3, l4));
          }
        }
      }
    }
    memset(nr, 0, sizeof(nr));
    memset(nw, 0, sizeof(nw));
  }
  cout<<ans;
  return 0;
}

Compilation message (stderr)

cubeword.cpp: In function 'int main()':
cubeword.cpp:67:16: warning: the address of 'void add(int&, long long int)' will never be NULL [-Waddress]
   67 |             if(add)
      |                ^~~

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