oj.uz

Submission #239020

# Submission time Handle Problem Language Result Execution time Memory
239020 2020-06-14T07:03:56 Z NONAME Mate (COCI18_mate) C++17
10 / 100
 290 ms 32760 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;

const int N = 2e5 + 10;
const int base = 1e9 + 7;

string s;
int c[2500][2500], res[2500][2500], res0[26][2500], sf[2500][26];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("in.txt", "r", stdin);

    cin >> s;
    int n = int(s.size());

    for (int i = 0; i < 2500; ++i) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; ++j)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % base;
    }

    for (int i = n - 1; i >= 0; --i)
    for (int j = 0; j < 26; j++) {
        sf[i][j] = (i + 1 == n ? 0 : sf[i + 1][j]);

        sf[i][j] += (s[i] == (j + 'a'));
    }

    for (int i = 0; i < n; ++i) {
        char c1 = s[i];

        for (int j = 0; j < 26; ++j)
        for (int l = -1; l < i; ++l) {
            int v = (c1 - 'a' + 1) + 29 * (j + 1);

            int vl = sf[i][j] - ((c1 - 'a') == j);

            res[v][l + 1] = (res[v][l + 1] + ((c[i][l + 1] * 1ll * vl) % base) % base);
        }
    }

//    for (int i = 0; i < n; ++i)
//    for (int j = i + 1; j < n; ++j) {
//        char c1 = s[i], c2 = s[j];
//        int v = (c1 - 'a' + 1) + 29 * (c2 - 'a' + 1);
//
//        for (int l = -1; l < i; ++l)
//            res[v][l + 1] = (res[v][l + 1] + c[i][l + 1]) % base;
//    }

    int q;
    cin >> q;
    while (q--) {
        int d;
        string t;
        cin >> d >> t;

        cout << res[(t[0] - 'a' + 1) + 29 * (t[1] - 'a' + 1)][d - 2] << "\n";
    }
}

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23168 KB Output is correct
2 Incorrect 23 ms 22912 KB Output isn't correct
3 Incorrect 23 ms 23040 KB Output isn't correct
4 Incorrect 26 ms 23040 KB Output isn't correct
5 Incorrect 53 ms 24744 KB Output isn't correct
6 Incorrect 59 ms 24824 KB Output isn't correct
7 Incorrect 47 ms 24696 KB Output isn't correct
8 Incorrect 47 ms 24744 KB Output isn't correct
9 Incorrect 290 ms 32760 KB Output isn't correct
10 Incorrect 283 ms 32760 KB Output isn't correct