Submission #197449

#	Time	Username	Problem	Language	Result	Execution time	Memory
197449		quocnguyen1012	Palindromic Partitions (CEOI17_palindromic)	C++14	0 / 100	9 ms	8184 KiB

palindromic

#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;

int mod[8] = {404545935, 277547886, 220295322, 397082103, 812451312, 988919419, 129255662, 48941114};

struct Data{
	ll a[8];

	void init (int val){
		for (int i=0; i<8; ++i)
			a[i] = val;
	}

	Data operator + (const Data & other) const{
		Data res;
		for (int i=0; i < 4; ++i){
			res.a[i] = (a[i] + other.a[i]) % mod[i];
		}
		return res;
	}
	Data operator - (const Data & other) const
	{
	  Data res;
	  for (int i = 0; i < 4; ++i){
      res.a[i] = (a[i] - other.a[i] + mod[i]) % mod[i];
	  }
	  return res;
	}
	bool operator == (const Data & other) const{
		for (int i=0; i<4; ++i){
			if (a[i] != other.a[i]) return false;
		}
		return true;
	}
	Data operator * (const Data & other) const{
		Data res;
		for (int i=0; i<4; ++i){
			res.a[i] = a[i] * other.a[i] % mod[i];
		}
		return res;
	}
};

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

Data getHash(int l, int r)
{
  Data tmp; tmp.init(POW[r - l + 1]);
  return Hash[r] - Hash[l - 1] * tmp;
}

void solve(void)
{
  string str; cin >> str;
  N = str.size();
  for (int i = 1; i <= N; ++i){
    Data tmp; tmp.init(str[i - 1]);
    Data btmp; btmp.init(base);
    Hash[i] = Hash[i - 1] * btmp + tmp;
  }
  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 (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:107: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:108: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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40