oj.uz

Submission #1104456

# Submission time Handle Problem Language Result Execution time Memory
1104456 2024-10-23T19:28:46 Z qrn Savez (COCI15_savez) C++14
108 / 120
 57 ms 23888 KB 
#include <bits/stdc++.h>
using namespace std;
 
template<class ISqr, class T>
ISqr& operator>>(ISqr& is, vector<T>& v) { for (auto& x : v) is >> x; return is; }
 
#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);
 
template <typename T>
void show(vector<T> &v) {
  for (T i : v) {
    cout << i << ' ';
  }
  cout << endl;
}

 
#define pb push_back
#define ins insert
#define fi first
#define se second
 
#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define sz(x) x.size()
#define int long long
#define _ << " " <<
#define no cout << "No" << endl;
#define yes cout << "Yes" << endl;
#define impos cout << -1 << endl;
 
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pii>
 
const int sz = 2e6 + 31;
const int base = 47;
const int mod = 1e18 + 3;

int mult(int a, int b) {
    return (a * b) % mod;
}

int add(int a, int b) {
    return a + b >= mod ? (a + b - mod) : a + b; 
}

map<int,int>idx;
int pw[sz];
void solve() {
    pw[0] = 1;
    for(int i = 1; i < sz; i++)   pw[i] = mult(pw[i-1], base);
    int n; cin >> n;
    vi dp(n + 1, 0);
    for(int i = 1; i <= n; i++) {
        dp[i] = 1;
        string s;
        cin >> s;
        reverse(ALL(s));
        string revs = s;
        reverse(ALL(s));
        int hashpre = 0, hashsuf = 0;
        for(int j = 0; j < sz(s); j++) {
            hashsuf = ((hashsuf + mult((revs[j] - 'a' + 1), pw[j])) + mod)  % mod;
            hashpre = ((hashpre + mult((s[j] - 'a' + 1), pw[j])) + mod) % mod;
            // cout << hashsuf << " " << hashpre << endl;
            if(hashpre == hashsuf) {
                auto it = idx.find(hashpre);
                if(it == idx.end()) continue;
                dp[i] = max(dp[i], dp[it->se] + 1);
                // cout << dp[i] << " " << dp[it->se] << endl;
            }
        }
        idx[hashpre] = i; // s-in hash valuesini at
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) ans = max(ans, dp[i]);
    cout << ans << endl;
}
 
signed main(){
    SPEED;
    int t = 1;
    // cin >> t;
    for(int cs = 1; cs <= t; cs++) {
        solve();
    }
}

Compilation message

savez.cpp: In function 'void solve()':
savez.cpp:66:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(int j = 0; j < sz(s); j++) {
      |                          ^

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15952 KB Output is correct
2 Correct 12 ms 15952 KB Output is correct
3 Incorrect 11 ms 15952 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15952 KB Output is correct
2 Correct 11 ms 15952 KB Output is correct
3 Correct 12 ms 15952 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 15952 KB Output is correct
2 Correct 20 ms 16020 KB Output is correct
3 Correct 27 ms 15952 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15952 KB Output is correct
2 Correct 30 ms 16224 KB Output is correct
3 Correct 36 ms 16216 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 16208 KB Output is correct
2 Correct 24 ms 16028 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16208 KB Output is correct
2 Correct 23 ms 16220 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 16220 KB Output is correct
2 Correct 24 ms 16208 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16464 KB Output is correct
2 Correct 25 ms 16464 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 17812 KB Output is correct
2 Correct 31 ms 17744 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 19024 KB Output is correct
2 Correct 38 ms 19036 KB Output is correct
3 Correct 57 ms 23888 KB Output is correct