记录编号	400024	评测结果	AAAAWWAWAA
题目名称	[HAOI 2009]求回文串	最终得分	70
用户昵称	不存在的	是否通过	未通过
代码语言	C++	运行时间	0.967 s
提交时间	2017-04-28 22:24:03	内存使用	9.98 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<ctime>
#include<algorithm>
#include<cstdlib>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
#define FILE "dealing"
#define LL long long 
#define up(i,j,n) for(LL i=j;i<=n;i++)
#define pii pair<LL,LL>
#define piii pair<LL,pair<LL,LL> >
template<typename T> inline bool chkmin(T &a,T b){return a>b?a=b,true:false;}
template<typename T> inline bool chkmax(T &a,T b){return a<b?a=b,true:false;}
namespace IO{
    char *fs,*ft,buf[1<<15];
    inline char gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
    inline LL read(){
        LL x=0;LL ch=gc();bool f=0;
        while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=gc();}
        while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();}
        return f?-x:x;
    }
}using namespace IO;
namespace OI{
    const LL maxn(1010000),mod(10000);
    char s[maxn];LL n;
    vector<LL> g[27];
    bool vis[maxn];
    LL c[maxn];
    inline LL lowbit(LL x){return x&-x;}
    inline void add(LL x,LL y){while(x<=n){c[x]+=y;x+=lowbit(x);}}
    inline LL get(LL x){LL sum=0;while(x>0)sum+=c[x],x-=lowbit(x);return sum;}
    void slove(){
        scanf("%s",s+1);
        n=strlen(s+1);LL x=0,cnt=0;
        up(i,1,n)x=x^(1<<(s[i]-'A'));
        for(LL i=0;i<26;i++)if(x&(1<<i))cnt++;
        if(cnt>1){printf("-1\n");return;}
        up(i,1,n)g[s[i]-'A'].push_back(i);
        up(i,1,n)add(i,1);
        LL ans=0;
        up(i,1,n){
            if(vis[i])continue;
            LL v=g[s[i]-'A'][g[s[i]-'A'].size()-1];
            if(i==v)ans+=(get(n)-get(i))/2;
            else ans+=get(n)-get(v);
            add(i,-1);add(v,-1);
            vis[i]=vis[v]=1;
            g[s[i]-'A'].erase(g[s[i]-'A'].end()-1);
        }
        printf("%I64d\n",ans);
    }
}
int main(){
    freopen("string!.in","r",stdin);
    freopen("string!.out","w",stdout);
    using namespace OI;
    slove();
    return 0;
}