oj.uz

Submission #632898

# Submission time Handle Problem Language Result Execution time Memory
632898 2022-08-21T06:10:54 Z racsosabe Savez (COCI15_savez) C++14
120 / 120
 112 ms 13980 KB 
#include <cstdio>
#include <iostream>
#include <map>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
using pii = pair<int, int>;
using llint = long long;

#define value first
#define idx second

const int MAXN = 1000010;
const int HASH1 = 3137;
const int HASH2 = 10007;
const int MOD = 1000000007;

map<pii, pii> dp;
int n, powh1[MAXN], powh2[MAXN], previous[MAXN], res, res_idx;
char s[MAXN];
vector<int> sol;

void solve(void) {
  memset(previous, -1, sizeof(previous));
  powh1[0] = powh2[0] = 1;
  for (int i = 1; i < MAXN; ++i) {
    powh1[i] = (llint)powh1[i - 1] * HASH1 % MOD;
    powh2[i] = (llint)powh2[i - 1] * HASH2 % MOD;
  }
  
  scanf("%d",&n);
  for (int j = 0; j < n; ++j) {
    scanf("%s",s);
    int m = strlen(s);
    int h_front1 = 0, h_back1 = 0;
    int h_front2 = 0, h_back2 = 0;
    int best = 0;
    for (int i = 0; i < m; ++i) {
      h_back1 = ((llint)h_back1 * HASH1 + int(s[m - 1 - i])) % MOD;
      h_front1 = (h_front1 + (llint)powh1[i] * int(s[i])) % MOD;

      h_back2 = ((llint)h_back2 * HASH2 + int(s[m - 1 - i])) % MOD;
      h_front2 = (h_front2 + (llint)powh2[i] * int(s[i])) % MOD;
      
      if (h_front1 == h_back1
	  && h_front2 == h_back2
	  && best < dp[{h_front1, h_front2}].value) {
	best = dp[{h_front1, h_front2}].value;
	previous[j] = dp[{h_front1, h_front2}].idx;
      }
    }
    dp[{h_front1, h_front2}] = pii(best + 1, j);

    if (best + 1 > res) {
      res = best + 1;
      res_idx = j;
    }    
  }
  
  printf("%d\n",res);
}

int main(void) {
  solve();
  return 0;
}

Compilation message

savez.cpp: In function 'void solve()':
savez.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   scanf("%d",&n);
      |   ~~~~~^~~~~~~~~
savez.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%s",s);
      |     ~~~~~^~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11988 KB Output is correct
2 Correct 13 ms 11988 KB Output is correct
3 Correct 11 ms 12028 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11980 KB Output is correct
2 Correct 10 ms 11988 KB Output is correct
3 Correct 12 ms 11976 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 12152 KB Output is correct
2 Correct 83 ms 12116 KB Output is correct
3 Correct 91 ms 13152 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12008 KB Output is correct
2 Correct 55 ms 12972 KB Output is correct
3 Correct 51 ms 13224 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 11988 KB Output is correct
2 Correct 33 ms 12952 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 11988 KB Output is correct
2 Correct 33 ms 12972 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 11972 KB Output is correct
2 Correct 39 ms 12928 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 11988 KB Output is correct
2 Correct 35 ms 13036 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 12032 KB Output is correct
2 Correct 47 ms 13160 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 12024 KB Output is correct
2 Correct 65 ms 13292 KB Output is correct
3 Correct 112 ms 13980 KB Output is correct