Submission #239053

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
239053	2020-06-14T09:22:46 Z	ne4eHbKa	Mate (COCI18_mate)	C++17	100 / 100	1304 ms	35076 KB

mate

#include <bits/stdc++.h>
using namespace std;

#define ft first
#define sd second

const int N = 2020;
const int A = 26;
const int md = 1e9 + 7;
const int Q = 5e5 + 5;

void madd(int &a, int b) {a += b; while(a < 0) a += md; while(a >= md) a -= md;}
int msum(int a, int b) {a += b; while(a < 0) a += md; while(a >= md) a -= md; return a;}
void mmul(int &a, int b) {a = 1ll * a * b % md;}
int mpro(int a, int b) {return 1ll * a * b % md;}

int mpow(int a, int p) {
    int ans = 1;
    for(int i = 1 << 30; i; i >>= 1) {
        mmul(ans, ans);
        if(p & i) mmul(ans, a);
    }
    return ans;
}

int n, q;
string s;
int t[Q];
char x[Q], y[Q];

int fact[N], ifact[N];

int C(int n, int k) {return mpro(mpro(ifact[k], ifact[n - k]), fact[n]);}

struct z {
    map<int, int> u;
    vector<int> c, g, f;
    int n;

    void add(int i, bool r) { u[i] += r; }

    void init() {
        n = u.size();
        c.resize(n);
        g.resize(n);
        f.resize(n);

        int i = 0;
        for(const auto &j : u) {
            c[i] = j.ft;
            g[i] = j.sd;
            f[i++] = 0;
        }

        for(int i = 0; i < n; ++i)
            for(int j = i; j < n; ++j)
                if(g[j]) madd(f[i], mpro(g[j], C(c[j], c[i])));
    }

    int get(int x) { return f[lower_bound(c.begin(), c.end(), x) - c.begin()]; }
} f[A][A];

int main() {
#ifdef _LOCAL
    freopen("in.txt", "r", stdin);
#endif

    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    for(int i = 0; i < N; ++i) fact[i] = !i ? 1 : mpro(fact[i - 1], i);
    for(int i = 0; i < N; ++i) ifact[i] = mpow(fact[i], md - 2);

    cin >> s >> q;

    n = s.size();
    for(int j = 0; j < n; ++j)
        for(int i = 0; i < j; ++i)
            f[s[i] - 'a'][s[j] - 'a'].add(i, true);

    for(int i = 0; i < q; ++i) {
        cin >> t[i] >> x[i] >> y[i];
        t[i] -= 2, x[i] -= 'a', y[i] -= 'a';
        f[x[i]][y[i]].add(t[i], false);
    }

    for(int i = 0; i < A; ++i)
        for(int j = 0; j < A; ++j)
            f[i][j].init();

    for(int i = 0; i < q; ++i)
        cout << f[x[i]][y[i]].get(t[i]) << '\n';
}

Compilation message

mate.cpp: In function 'int main()':
mate.cpp:83:15: warning: array subscript has type 'char' [-Wchar-subscripts]
         f[x[i]][y[i]].add(t[i], false);
               ^
mate.cpp:83:21: warning: array subscript has type 'char' [-Wchar-subscripts]
         f[x[i]][y[i]].add(t[i], false);
                     ^
mate.cpp:91:23: warning: array subscript has type 'char' [-Wchar-subscripts]
         cout << f[x[i]][y[i]].get(t[i]) << '\n';
                       ^
mate.cpp:91:29: warning: array subscript has type 'char' [-Wchar-subscripts]
         cout << f[x[i]][y[i]].get(t[i]) << '\n';
                             ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	1920 KB	Output is correct
2	Correct	12 ms	1536 KB	Output is correct
3	Correct	13 ms	1664 KB	Output is correct
4	Correct	19 ms	2176 KB	Output is correct
5	Correct	98 ms	7160 KB	Output is correct
6	Correct	96 ms	7416 KB	Output is correct
7	Correct	72 ms	6392 KB	Output is correct
8	Correct	66 ms	5880 KB	Output is correct
9	Correct	1251 ms	35076 KB	Output is correct
10	Correct	1304 ms	35064 KB	Output is correct