Codeforces и Polygon могут быть недоступны в период с 6 декабря, 22:00 (МСК) по 7 декабря, 00:00 (МСК) в связи с проведением технических работ. ×

Wrong Ans — Codechef Problem Compressed Strings

Правка en1, от saisumit, 2016-01-17 11:31:36

I am not able to figure out where i am getting wrong on this problem ...

https://www.codechef.com/problems/TACHEMIS

Your code here...


#include <bits/stdc++.h>


using namespace std;

#define pb push_back
#define ff first
#define ss second
typedef long long ll;




// Transform S into T.
// For example, S = "abba", T = "^#a#b#b#a#$".
// ^ and $ signs are sentinels appended to each end to avoid bounds checking
  vector<pair<char , long long >  > preProcess(  vector<pair<char , long long >  >& narr) {
  long long n = narr.size();
  vector<pair<char,long long > > arr ;
 // if (n == 0) return "^$";
  arr.pb(make_pair('^',0));

  for (long long i = 0; i < n; i++)
   { arr.pb(make_pair('#',0));
     arr.pb(make_pair(narr[i].ff , narr[i].ss)); }

  arr.pb(make_pair('#', 0));
  arr.pb(make_pair('$', 0));

  return arr;
}
void longestPalindrome(   vector<pair<char , long long >  > & arr ) {

    vector<pair<char , long long >  > T = preProcess(arr);

    long long n = T.size();
    long long *P = new long long [n];

     vector<ll>sum(n);

  long long C = 0, R = 0;
  for (long long i = 1; i < n-1; i++) {
   
    long long i_mirror = 2*C-i; // equals to i' = C - (i-C)

    P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;

    if( P[i] == R-i && R > i ) 
    for( int k = i + 1 ; k<= R - i ; k++ )
          sum[i]+=T[k].ss;
      
    else if(P[i] == P[i_mirror] && R > i )
         sum[i] = sum[i_mirror];
    
            // Attempt to expand palindrome centered at i
            while (T[i + 1 + P[i]].ff == T[i - 1 - P[i]].ff && T[i + 1 + P[i]].ss == T[i - 1 - P[i]].ss )
                        { sum[i] +=  T[i - 1 - P[i]].ss ;
                          P[i]++ ; }

            if((T[i + 1 + P[i]].ff == T[i - 1 - P[i]].ff ))
                          { sum[i] +=  min( T[i + 1 + P[i]].ss , T[i - 1 - P[i]].ss ) ;
                            P[i]++ ;
                             }

    // If palindrome centered at i expand past R,
    // adjust center based on expanded palindrome.
    if (i + P[i] > R) {
      C = i;
      R = i + P[i];
    }
  }
  long long ans = 0 ;

   for( long long i=0 ; i  < n ; i ++)
    {  if ( T[i].ff - 'A' >= 0 && T[i].ff - 'A' <=25)
          sum[i] += (T[i].ss) * (T[i].ss + 1) / 2 ;

         ans+=sum[i];
      // cout<< T[i].ff<<"  "<<T[i].ss<< " P[i]  "<< P[i] <<" Sum[i]  "<<sum[i]<<endl;

    }
 cout<<ans<<endl;


  delete[] P;

}

int  main()
{  cin.tie(0) ;
    long long t;
   string s;
   cin>> t;
   while(t--)
   { long long n ;
      cin >> n;
      string s;
      vector<pair<char , long long >  >arr(n) ;
      for(long long i = 0 ; i <n; i++)
       cin >> arr[i].ff >> arr[i].ss ;

      longestPalindrome(arr);

   }



}

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский saisumit 2016-01-17 11:31:36 2870 Initial revision (published)