oj.uz

Submission #71199

# Submission time Handle Problem Language Result Execution time Memory
71199 2018-08-24T08:07:54 Z octopuses 구간 성분 (KOI15_interval) C++17
100 / 100
 334 ms 872 KB 
//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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 440 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 3 ms 460 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 460 KB Output is correct
2 Correct 20 ms 460 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 3 ms 540 KB Output is correct
5 Correct 36 ms 592 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 724 KB Output is correct
2 Correct 152 ms 724 KB Output is correct
3 Correct 186 ms 724 KB Output is correct
4 Correct 156 ms 724 KB Output is correct
5 Correct 189 ms 724 KB Output is correct
6 Correct 155 ms 724 KB Output is correct
7 Correct 150 ms 760 KB Output is correct
8 Correct 166 ms 764 KB Output is correct
9 Correct 170 ms 872 KB Output is correct
10 Correct 152 ms 872 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 872 KB Output is correct
2 Correct 321 ms 872 KB Output is correct
3 Correct 327 ms 872 KB Output is correct
4 Correct 13 ms 872 KB Output is correct
5 Correct 334 ms 872 KB Output is correct