Advertisement
Guest User

Untitled

a guest
Apr 8th, 2012
339
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.18 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <iostream>
  4. #include <fstream>
  5. #include <sstream>
  6. #include <set>
  7. #include <map>
  8. #include <vector>
  9. #include <list>
  10. #include <algorithm>
  11. #include <cstring>
  12. #include <cmath>
  13. #include <string>
  14. #include <queue>
  15. #include <bitset>       //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
  16. #include <cassert>
  17. #include <iomanip>      //do setprecision
  18. #include <ctime>
  19. #include <complex>
  20. using namespace std;
  21.  
  22. #define FOR(i,b,e) for(int i=(b);i<(e);++i)
  23. #define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
  24. #define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
  25. #define REP(x, n) for(int x = 0; x < (n); ++x)
  26.  
  27. #define ST first
  28. #define ND second
  29. #define PB push_back
  30. #define MP make_pair
  31. #define LL long long
  32. #define ULL unsigned LL
  33. #define LD long double
  34.  
  35. const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
  36.  
  37. #define MR 1000010
  38.  
  39. int a[MR], b[MR], wa[MR], wb[MR];   //hieroglify i wystapienia hieroglifow
  40.  
  41. int main()
  42. {
  43.     memset(wa,-1,sizeof(wa));
  44.     memset(wb,-1,sizeof(wb));
  45.     int la, lb;
  46.     scanf("%d%d", &la, &lb);
  47.     REP(i,la)
  48.     {
  49.         scanf("%d", &a[i]);
  50.         wa[a[i]] = i;
  51.     }
  52.     REP(i,lb)
  53.     {
  54.         scanf("%d", &b[i]);
  55.         wb[b[i]] = i;
  56.     }
  57.     if(la == 1)
  58.     {
  59.         printf("%d\n", wb[a[0]] == -1 ? 0 : 1);
  60.         return 0;
  61.     }
  62.     if(lb == 1)
  63.     {
  64.         printf("%d\n", wa[b[0]] == -1 ? 0 : 1);
  65.         return 0;
  66.     }
  67.     int res = 0;    
  68.     int end = -1, x = wb[a[0]], y = wb[a[0]];
  69.     bool cond = 0;
  70.     REP(i,la)
  71.     {
  72.         if(wb[a[i]] == -1) break;   //nie ma hieroglifu w b
  73.         if(wb[a[i]] < x && !cond)   //od tego momentu trzeba wprowadzic warunek
  74.         {
  75.             cond = 1;
  76.             y = wb[a[i]];
  77.             end = i;                //przesun koniec
  78.         }
  79.         if(!cond)
  80.         {
  81.             if(wb[a[i]] < y)        
  82.                 break;
  83.             y = wb[a[i]];   //indeksy dalej rosna
  84.             end = i;            
  85.         }
  86.         else if(cond)       //spr, czy indeks trafia tam gdzie trzeba
  87.         {
  88.             if(wb[a[i]] < y || wb[a[i]] > x)    //nie wystepuje jako podciag
  89.                 break;
  90.             y = wb[a[i]];
  91.             end = i;    //przesun koniec
  92.         }
  93.     }  
  94.     if(end != -1) res = end+1;
  95.     if(res == la)
  96.     {
  97.         printf("%d\n", la);
  98.         return 0;
  99.     }
  100.     //przesuwaj poczatek o 1 i probuj poszerzac koniec
  101.     bool endza = 0;
  102.     FOR(i,1,la)
  103.     {      
  104.         if(wb[a[i]] == -1) continue;    //nie ma poczatku w b, od razu mozemy go pominac i sprawdzic nastepny
  105.         if(!endza && end < i) end = i;
  106.         if(wb[a[i]] < x) cond = 0;  //nie ma warunku
  107.         x = wb[a[i]];
  108.         while(true)
  109.         {
  110.             if(endza && end == i-1) break;      //mamy cale a
  111.             if(wb[a[(end+1)%la]] == -1) break;  //nie ma kolejnego hieroglifu w b -> nie da sie poszerzyc konca
  112.             if(wb[a[(end+1)%la]] < x && !cond)  //od tego momentu trzeba wprowadzic warunek
  113.             {
  114.                 cond = 1;
  115.                 y = wb[a[(end+1)%la]];
  116.                 if(end == la-1) endza = 1;      //end sie przekrecil
  117.                 end = (end+1)%la;               //przesun koniec                
  118.             }
  119.             if(!cond)
  120.             {
  121.                 if(wb[a[(end+1)%la]] < y)
  122.                     break;
  123.                 y = wb[a[(end+1)%la]];          //indeksy rosna dalej
  124.                 if(end == la-1) endza = 1;      //end sie przekrecil
  125.                 end = (end+1)%la;               //przesun koniec                
  126.             }
  127.             else        //spr czy indeks trafil tam gdzie trzeba
  128.             {
  129.                 if(wb[a[(end+1)%la]] < y || wb[a[(end+1)%la]] > x)
  130.                     break;
  131.                 y = wb[a[(end+1)%la]];          //indeksy rosna dalej
  132.                 if(end == la-1) endza = 1;      //end sie przekrecil
  133.                 end = (end+1)%la;  
  134.             }
  135.         }
  136.         //spr nowa dlugosc
  137.         if(!endza) res = max(res, end-i+1);
  138.         else res = max(res, end+1+la-i);
  139.     }
  140.     printf("%d\n", res);
  141.     return 0;
  142. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement