oj.uz

Submission #197448

# Submission time Handle Problem Language Result Execution time Memory
197448 2020-01-21T09:54:16 Z quocnguyen1012 Palindromic Partitions (CEOI17_palindromic) C++14
0 / 100
 9 ms 8184 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int base = 131;
const int maxn = 1e6 + 5;

ll Hash[maxn], POW[maxn];
int N;

ll getHash(int l, int r)
{
  return Hash[r] - Hash[l - 1] * POW[r - l + 1];
}

void solve(void)
{
  string str; cin >> str;
  N = str.size();
  for (int i = 1; i <= N; ++i){
    Hash[i] = Hash[i - 1] * base + str[i - 1];
  }
  int l1, r1, l2, r2;
  l1 = r1 = 1, l2 = r2 = N;
  int res = 0;
  ///assert(getHash(1, 2) == getHash(5, 6));
  while (true){
    //cerr << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << '\n';
    if (getHash(l1, r1) == getHash(l2, r2)){
      res += 2;
      ///cerr << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << '\n';
      l1 = r1 = r1 + 1;
      l2 = r2 = l2 - 1;
      if (r1 > l2){
        cout << res<< '\n';
        return;
      }
      if (r1 == l2){
        cout << res + 1 << '\n';
        return;
      }
    }
    else{
      ++r1; --l2;
      if (r1 >= l2){
        cout << res + 1<< '\n';
        return;
      }
    }
  }
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  POW[0] = 1;
  for (int i = 1; i < maxn; ++i)
    POW[i] = POW[i - 1] * base;
  int tc; cin >> tc;
  while (tc--){
    solve();
  }
}

Compilation message

palindromic.cpp: In function 'int main()':
palindromic.cpp:63:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:64:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

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