MCHAOS - Chaos Strings

Tác giả: hieult

Ngôn ngữ: C++

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000000001
#define maxn 100011
#define oo 1111111111
#define base 100000000
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
double const PI=4*atan(1);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;



int n,dem[maxn+10];
long long KQ=0;
char S[11];

struct chuoi{
      int id;
      char s[11];
      chuoi(){};
      bool operator <(chuoi T) const{
           return(strcmp(s,T.s)<0);
      }
};

chuoi A[maxn];

void reverse(char p[])
{
     int len=strlen(p);
     char t;
     for(int i=(--len), j=0; i>len/2; i--, j++)
     {
          // exchange elements
          t=p[i];
          p[i]=p[j];
          p[j]=t;
     }
}

void update(int u){
     while(u<=100000){
          dem[u]++;
          u+=u&-u; 
     }
}

long long tinh(int u){
     long long r = 0;
     while(u>0){
          //printf("%d\n",u);
          r+=dem[u];
          u-=u&-u;
     }
     return r;
}

int main()
{
   // freopen("MCHAOS.in","r",stdin);
     memset(dem,0,sizeof(dem));
     scanf("%d",&n);
     for(int i = 0;i<n;i++){
          scanf("%s",A[i].s);
         // printf("%s\n",A[i].s);
     }
     sort(A,A+n);
     for(int i = 0;i<n;i++){
           A[i].id = n-i;
           reverse(A[i].s);
           // printf("%s\n",A[i].s);
     }
     sort(A,A+n);
     for(int i = 0;i<n;i++){
            // printf("%d\n",A[i].id);
          KQ += tinh(A[i].id-1);
          update(A[i].id);
     }
     printf("%lld\n",KQ);
  //   getch();
}

Download