11557 - Code Theft

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

Re: 11557 - Code Theft

Post by Repon kumar Roy » Fri May 22, 2015 2:37 pm

I am using SA with segment Tree.
Getting WA?
Please Post some test case

Code: Select all


#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */
#define LMT                     1200006
#define ll                      long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define FOR(i,n)                for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define inf                     1<<30
#define lc                      ((n)<<1)
#define rc                      ((n)<<1 |1)
#define debug(x)                cout <<#x <<" -> " << x << endl;
#define EPS                     1e-9

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(int &x)
{
	register int c = gc();
	x = 0;
	int neg = 0;
	for(;((c<48 | c>57) && c != '-');c = gc());
	if(c=='-') {neg=1;c=gc();}
	for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
	if(neg) x=-x;
}

template <class T> inline T bigmod(T p,T e,T M){
	ll ret = 1;
	for(; e > 0; e >>= 1){
		if(e & 1) ret = (ret * p) % M;
		p = (p * p) % M;
	} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/*************************** END OF TEMPLATE ****************************/


string str;

map<string, int> kmp ;

string fileName[105];


int iAr[LMT];



#define LG 21

struct entry {
	int nr[2], p;
	
} L[LMT] , T[ LMT ];


int P[LG][LMT], N, i, stp, cnt;
int lcpAr[LMT];
int CT[LMT];
int PFA[LMT];

int cmp(struct entry a, struct entry b)
{
	return a.nr[0] == b.nr[0] ? (a.nr[1] < b.nr[1] ? 1 : 0) : (a.nr[0] < b.nr[0] ? 1 : 0);
	
}

void countingSort (entry v[] , int index , int len )
{
	int iM = -100;
	for(int  i = 0 ; i < len ; i ++ ){
		iM = max(iM , v[i].nr[index] + 1);
	}
	
	
	memset(CT ,0, (iM + 1) * sizeof(int));
	for(int i = 0 ; i< len; i ++ ) {
		CT[v[i].nr[index] + 1] ++;
	}
	
	PFA[0] = CT[0];
	for(int i = 1 ; i <= iM /* IM */ ; i ++ ) {
		PFA[i] = CT[i] + PFA[i-1];
	}
	
	for (int i = len - 1; i >=0 ; i -- ) {
		PFA[v[i].nr[index] + 1] --;
		T[PFA[v[i].nr[index] + 1]] = v[i];
	}
	
	for(int i = 0 ;i <len; i ++ ) v[i] = T[i];
	
}
void buildSA()
{
	
	
	for(int i = 0 ; i <N ; i ++ ) P[0][i] = iAr[i];
	for (stp = 1, cnt = 1; cnt >> 1 < N; stp ++, cnt <<= 1)
	{
		for (i = 0; i < N; i ++)
		{
			L[i].nr[0] = P[stp - 1][i];
			L[i].nr[1] = i + cnt < N ? P[stp - 1][i + cnt] : -1;
			L[i].p = i;
		}
		countingSort(L , 1 , N);
		countingSort(L , 0 , N );
		
		//sort(L, L + N , cmp);
		for (i = 0; i < N; i ++){
			
			P[stp][L[i].p] = i > 0 && L[i].nr[0] == L[i - 1].nr[0] && L[i].nr[1] == L[i - 1].nr[1] ? P[stp][L[i - 1].p] : i;
			
		}
		
		
	}
      L[N].p = N;
}

int lcp(int x, int y)
{
	int k, ret = 0;
	if (x == y) return N - x;
	for (k = stp - 1; k >= 0 && x < N && y < N; k --){
		
		if (P[k][x] == P[k][y])
			x += 1 << k, y += 1 << k, ret += 1 << k;
	}
	return ret;
	
}

void buildLCP()
{
      for(int i = 0; i< N ; i ++) {
            lcpAr[i]  = lcp(L[i].p, L[i+1].p);
      }
}

int ID[LMT];
int dumy = LMT - 105;

int seg[3*LMT];

void build(int n,int b,int e)
{
      if(b==e) {
            seg[n] = lcpAr[b];return;
      }
      int mid = (b+e)/2;
      build(lc, b, mid);
      build(rc, mid+1,e);
}

int query(int n,int b,int e,int i,int j)
{
      if(b > j || e < i ) return inf;
      if( b >= i && e <= j ) return seg[n];
      int mid = (b+e)/2;
      return min(query(lc, b, mid, i , j) , query(rc, mid + 1, e, i , j ));
}


int main()
{
	int n;
      //freopen("in.txt", "r", stdin);
      while(scanf("%d" , &n) == 1 ){
            
            int line = 0;
            int cnt = 0 ;
            for( int i = 0 ; i < n ; i ++ ) {
                  
                  getline(cin , str);
                  fileName[i] = str;
                  
                  
                  while (getline(cin,str) ) {
                        if(str.compare("***END***") == 0) break;
                        
                        
                        string tmp;
                        istringstream iss(str);
                        string s;
                        
                        int f = 0;
                        while (iss >> s)  {
                              if(f)tmp +=" ";
                              tmp += s;
                              f = 1;
                              
                        }
                        
                        if(kmp.count(tmp) == 0) {
                              
                              kmp[tmp] = line ++ ;
                        }
                        iAr[cnt] = kmp[ tmp ];
                        ID[cnt] = i ;
                        cnt ++;
                  }
                  
                  iAr[cnt ] = dumy + i ;
                  ID[cnt] = -1;
                  cnt ++;
            }
            
            
            while (getline(cin,str) ) {
                  if(str.compare("***END***") == 0) break;
                  
                  
                  string tmp;
                  istringstream iss(str);
                  string s;
                  
                  int f = 0;
                  while (iss >> s)  {
                        if(f)tmp +=" ";
                        tmp += s;
                        f = 1;
                        
                  }
                  if(kmp.count(tmp) == 0) {
                        kmp[tmp] = line ++ ;
                  }
                  iAr[cnt] = kmp[ tmp ];
                  ID[cnt] = n ;
                  cnt ++;
            }
            
            N = cnt;
            buildSA();
            buildLCP();
            
            int iM = 0;
            
            set<int> sl;
            int dif = 0;
            int val = 0;
            int begin , end;
            build(1,0,N-1);
            
            
            for( int i = 0 , j = 0  ;i < N && j < N ; ) {
                  
                  if(ID[ L[j].p ] == n ) val ++;
                  else dif ++;
                  if(val && dif ) {
                        int lp = query(1,0,N-1,i,j-1);
                        if(lp >= iM ) {
                              iM = lp;
                              begin = i ;
                              end =  j ;
                        }
                        
                        int l ;
                        for ( l =  i + 1; l <=  j ; l ++ ) {
                              int k = ID[L[l - 1].p];
                              if( k == n ) val --;
                              else dif --;
                              
                              if(val && dif ) {
                                    int lp = query(1,0,N-1,l,j-1);
                                    if(lp > iM ) {
                                          iM = lp;
                                          begin = l;
                                          end =  j ;
                                    }
                                    else break;

                              }
                              else break;
                        }
                        i = l;
                  }
                  j++;
                  
                  
            }
            
            printf("%d" , iM );
            if(iM ) {
                  for(int i = begin ; i <= end ; i ++ ) sl.insert(ID[L[i].p]);
                  
                  for(set<int>::iterator it= sl.begin() ; it != sl.end() ; it ++) {
                        if( *it != n )printf(" %s" , fileName[*it].c_str() );
                  }
            }
            
            printf("\n");
            kmp.clear();
      }
	
	return 0;
}



Post Reply

Return to “Volume 115 (11500-11599)”