oj.uz

Submission #23199

# Submission time Handle Problem Language Result Execution time Memory
23199 2017-05-04T12:04:11 Z model_code Savez (COCI15_savez) C++11
120 / 120
 136 ms 14984 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:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
                 ^
savez.cpp:35:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",s);
                  ^

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14720 KB Output is correct
2 Correct 13 ms 14720 KB Output is correct
3 Correct 9 ms 14720 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 14852 KB Output is correct
2 Correct 123 ms 14852 KB Output is correct
3 Correct 126 ms 14852 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14720 KB Output is correct
2 Correct 49 ms 14852 KB Output is correct
3 Correct 69 ms 14984 KB Output is correct

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 14720 KB Output is correct
2 Correct 33 ms 14720 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 14720 KB Output is correct
2 Correct 29 ms 14720 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 14720 KB Output is correct
2 Correct 33 ms 14720 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 14720 KB Output is correct
2 Correct 43 ms 14720 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 14720 KB Output is correct
2 Correct 59 ms 14720 KB Output is correct
3 Correct 113 ms 14720 KB Output is correct