oj.uz

Submission #145036

# Submission time Handle Problem Language Result Execution time Memory
145036 2019-08-18T13:17:23 Z Mihnea Mate (COCI18_mate) C++14
0 / 100
 677 ms 109532 KB 
#include<iostream>
#include<cstdio>
#include<cstring>
#define MOD 1000000007
using namespace std;
long long I;
long long a[2005][2005],b[2005][30],poz[30][2005],sol[2005][30][30],D[2005][30][30];
char s[2005],X,Y;
int main(){
    scanf("%s", (s+1));
    int n=strlen((s+1));
    a[0][0]=1;
    for(int i=1;i<=n;i++){
        a[i][0]=a[i][i]=1;
        for(int j=1;j<i;j++){
            a[i][j]=a[i-1][j-1]+a[i-1][j];
            if(a[i][j]>=MOD)
                a[i][j]-=MOD;
        }
    }
    for(int i=1;i<=n;i++)
        poz[s[i]-'a'][ ++poz[s[i]-'a'][0] ]=i;
    for(int i=n;i>=1;i--)
        for(int j=0;j<26;j++)
            if(s[i]=='a'+j)
                b[i][j]=1+b[i+1][j];
            else
                b[i][j]=b[i+1][j];
    for(int i=n;i>=1;i--)
        for(int j=0;j<26;j++)
            for(int k=0;k<26;k++)
                if(s[i]=='a'+j)
                    D[i][j][k]=b[i+1][k];
                else
                    D[i][j][k]=D[i+1][j][k];
    for(int i=2;i<=n;i++)
        for(int j=0;j<26;j++)
            for(int t=1;t<=poz[j][0];t++){
                int h=poz[j][t];
                if(h>=i-1)
                    for(int k=0;k<26;k++){
                        sol[i][j][k]+=(D[h][j][k]*a[h-1][i-2])%MOD;
                        if(sol[i][j][k]>=MOD)
                            sol[i][j][k]-=MOD;
                    }
            }
    scanf("%lld",&n);
    while(n!=0){
        scanf("%lld %c %c",&I,&X,&Y);
        printf("%lld\n",sol[I][X-'a'][Y-'a']);
        n--;
    }
    return 0;
}

Compilation message

mate.cpp: In function 'int main()':
mate.cpp:47:20: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'int*' [-Wformat=]
     scanf("%lld",&n);
                  ~~^
mate.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", (s+1));
     ~~~~~^~~~~~~~~~~~~
mate.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
mate.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %c %c",&I,&X,&Y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 13 ms 2296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 14 ms 2320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 18 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 59 ms 9208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 63 ms 9336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 53 ms 9340 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 49 ms 8952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 677 ms 109496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 635 ms 109532 KB Execution killed with signal 11 (could be triggered by violating memory limits)