oj.uz

Submission #145716

# Submission time Handle Problem Language Result Execution time Memory
145716 2019-08-20T20:49:16 Z AlexPascu007 Mate (COCI18_mate) C++
100 / 100
 554 ms 53700 KB 
#include <cstdio>
#include <cstring>
#include <vector>
#define mod 1000000007
#define DIM 2002
using namespace std;
char p,u,s[DIM];
long long n,i,j,k,t,l,c[DIM][DIM],r[DIM][26],d[DIM][26][26],sol[DIM][26][26];
vector<long long> poz[26];
int main() {
    scanf("%s",s+1);
    n=strlen(s+1);
    c[0][0]=1;
    for (i=1;i<=n;i++) {
        c[i][0]=1;
        for (j=1;j<=i;j++) {
            c[i][j]=c[i-1][j-1]+c[i-1][j];
            if (c[i][j]>=mod)
                c[i][j]-=mod;
        }
    }
    for (i=1;i<=n;i++)
        poz[s[i]-'a'].push_back(i);
    for (i=n;i>=1;i--) {
        for (j=0;j<26;j++) {
            if (s[i]==j+'a')
                r[i][j]=1+r[i+1][j];
            else
                r[i][j]=r[i+1][j];
        }
    }
    for (i=n;i>=1;i--) {
        for (j=0;j<26;j++) {
            for (k=0;k<26;k++) {
                if (s[i]==j+'a')
                    d[i][j][k]=r[i+1][k];
                else
                    d[i][j][k]=d[i+1][j][k];
            }
        }
    }
    for (l=2;l<=n;l++) {
        for (j=0;j<26;j++) {
            for (t=0;t<poz[j].size();t++) {
                i=poz[j][t];
                if (i>=l-1) {
                    for (k=0;k<26;k++) {
                        sol[l][j][k]+=d[i][j][k]*c[i-1][l-2]%mod;
                        if (sol[l][j][k]>=mod)
                            sol[l][j][k]-=mod;
                    }
                }
            }
        }
    }
    scanf("%lld",&t);
    while (t--) {
        scanf("%lld %c %c",&l,&p,&u);
        printf("%lld\n",sol[l][p-'a'][u-'a']);
    }
    return 0;
}

Compilation message

mate.cpp: In function 'int main()':
mate.cpp:44:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (t=0;t<poz[j].size();t++) {
                      ~^~~~~~~~~~~~~~
mate.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",s+1);
     ~~~~~^~~~~~~~~~
mate.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&t);
     ~~~~~^~~~~~~~~~~
mate.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %c %c",&l,&p,&u);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1272 KB Output is correct
2 Correct 8 ms 1144 KB Output is correct
3 Correct 8 ms 1144 KB Output is correct
4 Correct 13 ms 1272 KB Output is correct
5 Correct 46 ms 5240 KB Output is correct
6 Correct 53 ms 5496 KB Output is correct
7 Correct 47 ms 4984 KB Output is correct
8 Correct 37 ms 4856 KB Output is correct
9 Correct 554 ms 53624 KB Output is correct
10 Correct 540 ms 53700 KB Output is correct