Cod sursa(job #1491070)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 24 septembrie 2015 19:03:51
Problema Abc2 Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXCUV 50000
char *buffer;
long long v[MAXCUV];
int conb;
void myqsort(int begin,int end){
    int b=begin,e=end;
    long long aux,pivot=v[(b+e)/2];
    while(b<=e){
        while(v[b]<pivot) b++;
        while(v[e]>pivot) e--;
        if(b<=e){
            aux=v[b];
            v[b]=v[e];
            v[e]=aux;
            b++;e--;
        }
    }
    if(begin<e) myqsort(begin,e);
    if(b<end) myqsort(b,end);
}
inline int cauta(int m,long long nr){
    int pas,rez,flag=0;
    rez=0;
    for(pas=1<<16;pas;pas>>=1)
        if(pas+rez<m&&v[pas+rez]<nr)
             rez+=pas;
    if((rez+1<m&&v[rez+1]==nr)||v[0]==nr)
        flag=1;
    return flag;
}
inline void blanc(int lSize){
    while(conb<lSize&&(buffer[conb]<'a'||buffer[conb]>'c'))
        conb++;
}
int main(){
    FILE*fi,*fout;
    int con,m,n,l,i,lSize,x;
    long long nr,p3;
    fi=fopen("abc2.in" ,"rb");
    fout=fopen("abc2.out" ,"w");
    fseek(fi,0,SEEK_END);
    lSize=ftell(fi);
    rewind(fi);
    buffer=(char*) malloc(sizeof(char)*lSize);
    fread(buffer,1,lSize,fi);
    n=0;
    while(buffer[n]>='a'&&buffer[n]<='c')
        n++;
    conb=n;
    blanc(lSize);
    m=0;
    while(conb<lSize){
        l=0;
        while(conb<lSize&&buffer[conb]>='a'&&buffer[conb]<='c'){
            v[m]=v[m]*3+buffer[conb]-'a';
            l++;
            conb++;
        }
        blanc(lSize);
        m++;
    }
    p3=1;
    for(i=0;i<l-1;i++)
        p3*=3;
    myqsort(0,m-1);
    nr=0;
    for(i=0;i<l;i++)
        nr=nr*3+buffer[i]-'a';
    con=cauta(m,nr);
    for(i=l;i<n;i++){
        nr=(nr-p3*(buffer[i-l]-'a'))*3+buffer[i]-'a';
        con+=cauta(m,nr);
    }
    fprintf(fout,"%d" ,con);
    fclose(fi);
    fclose(fout);
    return 0;
}