Submission #1134776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134776		orzdraiduwu	Palindromic Partitions (CEOI17_palindromic)	C++20	0 / 100	0 ms	320 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;
#define int long long

// // i remember not being to solve this in conest
// // me = retarded
// void solve() {
//   int n, k; cin >> n >> k;
//   if(k % 2 == 1 or k > n*(n-1)) {
//     cout << "NO\n";
//     return;
//   }

//   vector<int> ve(n);
//   // if(n % 2 == 0) {
//   for(int i = 0 ; i < n ; i++) ve[i] = i+1;
//   cout << "YES\n";
//   int r = 0, v = 2*(n-1);
//   for(int i = 0, j = n-1 ; i < j ; i++, j--) {
//     if(r + v <= k) {
//       r += v;
//       swap(ve[i], ve[j]);
//     }

//     v -= 4;
//   }

//   // cout << r << " " << k << '\n';
//   int q = 0;
//   if(r != k) {
//     for(int i = 0 ; i < n-1 ; i++) {
//       q += abs(ve[i+1] - i - 1);
//       q += abs(ve[i] - i - 2);
//       q -= abs(ve[i] - i - 1);
//       q -= abs(ve[i+1] - i - 2);
//       if(r + q == k) {
//         swap(ve[i], ve[i+1]);
//         break;
//       }
      
//       q = 0;
//     }
//   }
  
//   for(int i = 0 ; i < n ; i++) cout << ve[i] << ' ';
//   cout << '\n';
//   return;
// }

const int MOD = 1000000007;
const int BA = 29;
void solve() {
  string g; cin >> g;
  int r = 0;
  // if(g.size() % 2 == 1) r = 1;
  int ha = 0, hb = 0, pb = 1;
  int i = 0, j = g.size() - 1;
  // retardation tm
  while(j >= i) {
    ha = (g[i]*pb + ha)%MOD;
    hb = (g[j] + pb*hb)%MOD; // silly me.
    pb = (pb*BA)%MOD;
    i++;
    j--;
    // cout << ha << " " << hb << '\n';
    if(ha == hb) {
      // cout << i << " " << j << '\n';
      ha = 0;
      hb = 0;
      pb = 1;
      if(i != j) r += 2;
      else r += 1;
      continue;
    }

  }

  if(ha > 0 or hb > 0) r++;
  cout << r << '\n';
}

signed main() {
  int t; cin >> t;
  while(t--) solve();
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 20
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40