oj.uz

Submission #1043053

# Submission time Handle Problem Language Result Execution time Memory
1043053 2024-08-03T19:58:07 Z earlyamazon Savez (COCI15_savez) C++14
120 / 120
 57 ms 14016 KB 
// wzorcowka autorow zadania (COCI 2015/2016)

#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:35:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |   scanf("%d",&n);
      |   ~~~~~^~~~~~~~~
savez.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%s",s);
      |     ~~~~~^~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12888 KB Output is correct
2 Correct 7 ms 12888 KB Output is correct
3 Correct 6 ms 13004 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12892 KB Output is correct
2 Correct 6 ms 12964 KB Output is correct
3 Correct 6 ms 12892 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 13744 KB Output is correct
2 Correct 56 ms 13648 KB Output is correct
3 Correct 57 ms 13648 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12892 KB Output is correct
2 Correct 26 ms 13652 KB Output is correct
3 Correct 30 ms 13652 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 13652 KB Output is correct
2 Correct 19 ms 13764 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 13652 KB Output is correct
2 Correct 19 ms 13564 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 13660 KB Output is correct
2 Correct 20 ms 13660 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 13652 KB Output is correct
2 Correct 19 ms 13660 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 13648 KB Output is correct
2 Correct 28 ms 13660 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 13916 KB Output is correct
2 Correct 35 ms 13904 KB Output is correct
3 Correct 54 ms 14016 KB Output is correct