Submission #71199

#	Time	Username	Problem	Language	Result	Execution time	Memory
71199		octopuses	구간 성분 (KOI15_interval)	C++17	100 / 100	334 ms	872 KiB

interval

//Giorgi Kldiashvili

#include <bits/stdc++.h>

#define ll long long
#define P 100003
#define Q 100019
#define M 1000000007ll
#define N 1000000009ll


using namespace std;

ll C[26], D[26];
pair < ll, ll > now;
set < pair < ll, ll > > S;
set < pair < ll, ll > >::iterator it;
char ch[1520];
int a[1520], b[1520];
int A[26];
int n, m;

int main()
{
  scanf("%s", &ch); n = strlen(ch);
  for(int i = 1; i <= n; ++ i)
    a[i] = ch[i - 1] - 'a';
  scanf("%s", &ch); m = strlen(ch);
  for(int i = 1; i <= m; ++ i)
    b[i] = ch[i - 1] - 'a';
  C[0] = P;
  D[0] = Q;
  for(int i = 1; i < 26; ++ i)
  {
    C[i] = (C[i - 1] * P) % M;
    D[i] = (D[i - 1] * Q) % N;
  }
  for(int len = min(n, m); len >= 1; -- len)
  {
    for(int i = 0; i < 26; ++ i) A[i] = 0;
    for(int i = 1; i <= len; ++ i) A[a[i]] ++;
    now = {0, 0};
    for(int i = 0; i < 26; ++ i)
    {
      now.first = ((A[i] * C[i]) % M + now.first) % M;
      now.second = ((A[i] * D[i]) % N + now.second) % N;
    }
    S.clear();
    S.insert(now);
    for(int i = 1; i + len <= n; ++ i)
    {
      if(a[i] != a[i + len])
      {
        now.first = (now.first - (A[a[i]] * C[a[i]]) % M + M) % M;
        now.second = (now.second - (A[a[i]] * D[a[i]]) % N + N) % N;
        now.first = (now.first - (A[a[i + len]] * C[a[i + len]]) % M + M) % M;
        now.second = (now.second - (A[a[i + len]] * D[a[i + len]]) % N + N) % N;
        A[a[i]] --; A[a[i + len]] ++;
        now.first = ((A[a[i + len]] * C[a[i + len]]) % M + now.first) % M;
        now.second = ((A[a[i + len]] * D[a[i + len]]) % N + now.second) % N;
        now.first = ((A[a[i]] * C[a[i]]) % M + now.first) % M;
        now.second = ((A[a[i]] * D[a[i]]) % N + now.second) % N;
      }
      S.insert(now);
    }
    for(int i = 0; i < 26; ++ i) A[i] = 0;
    for(int i = 1; i <= len; ++ i) A[b[i]] ++;
    now = {0, 0};
    for(int i = 0; i < 26; ++ i)
    {
      now.first = ((A[i] * C[i]) % M + now.first) % M;
      now.second = ((A[i] * D[i]) % N + now.second) % N;
    }
    it = S.lower_bound(now);
    if(it != S.end() && *it == now)
      return printf("%d", len), 0;
    for(int i = 1; i + len <= m; ++ i)
    {
      if(b[i] != b[i + len])
      {
        now.first = (now.first - (A[b[i]] * C[b[i]]) % M + M) % M;
        now.second = (now.second - (A[b[i]] * D[b[i]]) % N + N) % N;
        now.first = (now.first - (A[b[i + len]] * C[b[i + len]]) % M + M) % M;
        now.second = (now.second - (A[b[i + len]] * D[b[i + len]]) % N + N) % N;
        A[b[i]] --; A[b[i + len]] ++;
        now.first = ((A[b[i + len]] * C[b[i + len]]) % M + now.first) % M;
        now.second = ((A[b[i + len]] * D[b[i + len]]) % N + now.second) % N;
        now.first = ((A[b[i]] * C[b[i]]) % M + now.first) % M;
        now.second = ((A[b[i]] * D[b[i]]) % N + now.second) % N;
      }
      it = S.lower_bound(now);
      if(it != S.end() && *it == now)
        return printf("%d", len), 0;
    }
  }
  printf("0\n");
}

Compilation message (stderr)

interval.cpp: In function 'int main()':
interval.cpp:25:18: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1520]' [-Wformat=]
   scanf("%s", &ch); n = strlen(ch);
               ~~~^
interval.cpp:28:18: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1520]' [-Wformat=]
   scanf("%s", &ch); m = strlen(ch);
               ~~~^
interval.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", &ch); n = strlen(ch);
   ~~~~~^~~~~~~~~~~
interval.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", &ch); m = strlen(ch);
   ~~~~~^~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 31 / 31
• Subtask 4: 39 / 39