Submission #1542088
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define eps 1e-13
#define PI 3.141592653589793238L
#define INF 1000000011
#define INFLL 1000000000000000011LL
// #define space printf(" ")
#define endl printf("\n")
#define vi vector<int>
#define vll vector<long long>
#define vc vector<char>
#define vs vector<string>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pil pair<int, long long>
#define pli pair<long long, int>
#define pcc pair<char, char>
#define pdd pair<double, double>
#define mp make_pair
#define F first
#define S second
#define pb(x) push_back(x)
#define fo(i,a,n) for(i = (a); i < (n); i++)
#define sd(x) scanf("%d", &(x))
#define pd(x) printf("%d", (x))
#define pdn(x) printf("%d\n", (x))
#define slld(x) scanf("%lld", &(x))
#define plld(x) printf("%lld", (x))
#define plldn(x) printf("%lld\n", (x))
#define sllf(x) scanf("%llf", &(x))
#define pllf(x) printf("%.9llf", (x))
#define pllfn(x) printf("%.9llf\n", (x))
#define sch(x) scanf("%c", &(x))
#define pch(x) printf("%c", (x))
#define pchn(x) printf("%c\n", (x))
#define gtl(x) getline(cin, (x))
#define flsh fflush(stdout)
#define sws ios_base::sync_with_stdio(false); cin.tie(0)
#define gcd __gcd
#define clr(x) memset(x,0,sizeof(x))
#define all(a) (a).begin(), (a).end()
#define foreach(i,a) for(__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)
#define sz(a) (int)((a).size())
#define io_file freopen("D:/Coding Problems/Contest/input_file.in", "r", stdin);freopen("D:/Coding Problems/Contest/output_file.out", "w", stdout)
ll modx(ll Base, ll exponent)
{
ll ans = 1;
if(Base == 1)
return Base;
while(exponent)
{
if(exponent & 1)
ans = (ans * Base)%mod;
Base = (Base * Base)%mod;
exponent = exponent >> 1;
}
return ans;
}
ll inmodx(ll num)
{
return (modx(num, mod-2LL));
}
bool cmp()//true for a before b
{
bool ans = 0;
return ans;
}
struct ST_Node
{
ST_Node()
{
return;
}
void assign_value_(int val)
{
return;
}
void merge_nodes_(ST_Node& left, ST_Node& right)
{
return;
}
};
const int N = (2e5) + 9;
const int M = (N<<2) + 9;
const int LOGN = ((int)log2(N)) + 3;
const int LOGM = ((int)log2(M)) + 3;
// This is a property of abhishek_1997
ll hs[2][N], rhs[2][N], pp[2][N], ipp[2][N];//Check the limits
pll x[2];
void hash_setup()
{
int i, j;
pp[0][1] = 29LL;
pp[1][1] = 31LL;
fo(j,0,2)
{
pp[j][0] = ipp[j][0] = 1LL;
ipp[j][1] = inmodx(pp[j][1]);
fo(i,2,N)
{
pp[j][i] = (pp[j][i-1]*pp[j][1])%mod;
ipp[j][i] = (ipp[j][i-1]*ipp[j][1])%mod;
}
}
}
void str_hash(string s_)
{
int n, i, j;
n = s_.length();
fo(j,0,2)
{
hs[j][0] = 0LL;
fo(i,1,n+1)
hs[j][i] = (hs[j][i-1] + ((ll)(s_[i-1]-'a'+1)*pp[j][i]))%mod;//Check this statement for the type of char
rhs[j][0] = 0LL;
fo(i,1,n+1)
rhs[j][i] = (rhs[j][i-1] + ((ll)(s_[n-i]-'a'+1)*pp[j][i]))%mod;//Check this statement for the type of char
}
return;
}
pll sub_string(int j, int i)//To get the substring s[j]s[j+1].....s[i-1]s[i] (1-indexed)
{
return mp((ipp[0][j-1]*((hs[0][i]-hs[0][j-1]+mod)%mod))%mod, (ipp[1][j-1]*((hs[1][i]-hs[1][j-1]+mod)%mod))%mod);
}
pll rsub_string(int j, int i)//To get the substring s[j]s[j+1].....s[i-1]s[i] (1-indexed)
{
return mp((ipp[0][j-1]*((rhs[0][i]-rhs[0][j-1]+mod)%mod))%mod, (ipp[1][j-1]*((rhs[1][i]-rhs[1][j-1]+mod)%mod))%mod);
}
bool is_palin(int l, int r, int n)
{
x[0] = sub_string(l,r);
x[1] = rsub_string(n-r+1,n-l+1);
return (x[0] == x[1]);
}
int binsea(int l, int r, int n, int ind)
{
if(l > r)
return 0;
int mid = (l+r)>>1;
if(is_palin(ind-mid,ind+mid,n))
return max(mid, binsea(mid+1,r,n,ind));
return binsea(l,mid-1,n,ind);
}
int binsea(int l, int r, int n, int ind1, int ind2)
{
if(l > r)
return 0;
int mid = (l+r)>>1;
if(is_palin(ind1-mid,ind2+mid,n))
return max(mid, binsea(mid+1,r,n,ind1,ind2));
return binsea(l,mid-1,n,ind1,ind2);
}
ll cnt[26];
ll func(ll n)
{
ll ans = (n*(n+1LL));
ans >>= 1;
return ans;
}
int main()
{
sws;
// clock_t clk;
// clk = clock();
// io_file;
// srand (time(NULL));
//Code here
hash_setup();
string s;
int i, n, len;
ll ans = 0LL, val = 0LL;
cin >> s;
n = s.length();
/*str_hash(s);
fo(i,1,n+1)
{
ans += ((ll)i);
len = binsea(0,min(i,n+1-i)-1,n,i);
val += ((ll)(len+1));
// cerr << "hi : " << i << " " << len << '\n';
}
fo(i,1,n)
{
if(s[i-1] == s[i])
{
len = binsea(0,min(i,n-i)-1,n,i,i+1);
val += ((ll)(len+1));
// cerr << "hey : " << i << " " << len << '\n';
}
}
// cerr << ans << " " << val << '\n';
ans += (1LL - val);*/
fo(i,0,n)
cnt[s[i]-'a']++;
ans = func((ll)n)+1LL;
fo(i,0,26)
ans -= func(cnt[i]);
cout << ans;
// Code ends here
// clk = clock() - clk;
// cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << "\n";
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Reverse and Compare |
User |
already_last |
Language |
C++14 (GCC 5.4.1) |
Score |
500 |
Code Size |
5044 Byte |
Status |
AC |
Exec Time |
6 ms |
Memory |
8912 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
500 / 500 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
5 ms |
8448 KB |
sample_02.txt |
AC |
5 ms |
8448 KB |
sample_03.txt |
AC |
5 ms |
8448 KB |
subtask_1_01.txt |
AC |
5 ms |
8448 KB |
subtask_1_02.txt |
AC |
6 ms |
8912 KB |
subtask_1_03.txt |
AC |
5 ms |
8448 KB |
subtask_1_04.txt |
AC |
5 ms |
8448 KB |
subtask_1_05.txt |
AC |
5 ms |
8448 KB |
subtask_1_06.txt |
AC |
5 ms |
8448 KB |
subtask_1_07.txt |
AC |
5 ms |
8448 KB |
subtask_1_08.txt |
AC |
6 ms |
8912 KB |
subtask_1_09.txt |
AC |
6 ms |
8912 KB |
subtask_1_10.txt |
AC |
6 ms |
8912 KB |
subtask_1_11.txt |
AC |
6 ms |
8912 KB |
subtask_1_12.txt |
AC |
6 ms |
8912 KB |
subtask_1_13.txt |
AC |
6 ms |
8912 KB |
subtask_1_14.txt |
AC |
6 ms |
8912 KB |
subtask_1_15.txt |
AC |
6 ms |
8912 KB |
subtask_1_16.txt |
AC |
6 ms |
8912 KB |
subtask_1_17.txt |
AC |
6 ms |
8912 KB |