Cod sursa(job #2970392)

Utilizator user12345user user user user12345 Data 24 ianuarie 2023 23:45:43
Problema Matrix Scor 35
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.21 kb
#include<bits/stdc++.h>
using namespace std;

ifstream fin("matrix.in");
ofstream fout("matrix.out");

vector <int> v[1001][26];
int fr[1001][26];
int n, X1, Y1, X2, Y2, res[26], f[26];

struct nod {
    int fr[26] = { 0 };
};

int main()
{
    int aux;
    fin >> n >> aux;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            char c;
            fin >> c;
            v[i][c - 'a'].push_back(j);
        }

    for (int i = 1; i <= aux; i++)
        for (int j = 1; j <= aux; j++)
        {
            char c;
            fin >> c;
            res[c - 'a']++;
        }

    int cnt = 0;

    for (int i = 1; i <= n - aux + 1; i++)
    {
        for (short k = 0; k < 26; k++)
            f[k] = 0;

        for (int j = 1; j < aux; j++)
        {
            for (short k = 0; k < 26; k++)
            {
                fr[j][k] = 0;
                int l = 0, r = v[j][k].size() - 1, poz1 = -1, poz2;

                while (l <= r)
                {
                    int m = (l + r) >> 1;

                    if (v[j][k][m] >= i)
                    {
                        poz1 = m;
                        r = m - 1;
                    }
                    else
                        l = m + 1;
                }

                if (poz1 == -1 || v[j][k][poz1] > i + aux - 1)
                    continue;

                l = poz1, r = v[j][k].size() - 1;

                while (l <= r)
                {
                    int m = (l + r) >> 1;

                    if (v[j][k][m] <= i + aux - 1)
                    {
                        poz2 = m;
                        l = m + 1;
                    }
                    else
                        r = m - 1;
                }

                fr[j][k] = poz2 - poz1 + 1;
                f[k] += poz2 - poz1 + 1;
            }
        }

        for (int j = aux; j <= n; j++)
        {
            bool ok = true;

            for (short k = 0; k < 26; k++)
            {
                int l = 0, r = v[j][k].size() - 1, poz1 = -1, poz2;

                while (l <= r)
                {
                    int m = (l + r) >> 1;

                    if (v[j][k][m] >= i)
                    {
                        poz1 = m;
                        r = m - 1;
                    }
                    else
                        l = m + 1;
                }

                if (poz1 == -1 || v[j][k][poz1] > i + aux - 1)
                    continue;

                l = poz1, r = v[j][k].size() - 1;

                while (l <= r)
                {
                    int m = (l + r) >> 1;

                    if (v[j][k][m] <= i + aux - 1)
                    {
                        poz2 = m;
                        l = m + 1;
                    }
                    else
                        r = m - 1;
                }

                fr[j][k] = poz2 - poz1 + 1;
                f[k] += poz2 - poz1 + 1;
                f[k] -= fr[j - aux][k];
                ok &= (f[k] == res[k]);
            }

            if (ok)
                cnt++;
        }
    }

    fout << cnt;

    return 0;
}