Advertisement
Guest User

Untitled

a guest
Apr 21st, 2017
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 10.69 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cassert>
  3. #include <cstring>
  4. #include <cstdlib>
  5. #include <cctype>
  6. #include <cstdint>    
  7. #include "immintrin.h"
  8. using namespace std;
  9.  
  10. const int N = (int)3e6 + 10;
  11. const int LEN = (int)1e5 + 10;
  12. #ifdef _MSC_VER
  13.     #define ALIGN(x) __declspec(align(x))
  14.     #define ATTR
  15. #else
  16.     #define ALIGN(x) __attribute__((aligned(x)))
  17.     #define ATTR __attribute__((target("avx")))
  18. #endif
  19. ALIGN(16) char str[N];
  20. ALIGN(16) char rStr[LEN];
  21. ALIGN(16) char result[N];
  22.  
  23. ATTR int is_equal(const char* src_1, const char* src_2, size_t size)
  24. {
  25.     const char* head_1 = (const char*)src_1;
  26.     const char* head_2 = (const char*)src_2;
  27.     size_t tail_n = 0;
  28.    
  29.     while (((uintptr_t)head_1 % 16) != 0 && tail_n < size)
  30.     {                                
  31.         if (*head_1 != *head_2)
  32.             return 0;
  33.         head_1++, head_2++, tail_n++;
  34.     }
  35.    
  36.     const __m128i* src1 = (const __m128i*)head_1;
  37.     const __m128i* src2 = (const __m128i*)head_2;
  38.     const size_t n = (size - tail_n) / 32;
  39.    
  40.     for (size_t i = 0; i < n; ++i, src1 += 2, src2 += 2)
  41.     {
  42.         __m128i mm11 = _mm_load_si128(src1);
  43.         __m128i mm12 = _mm_load_si128(src1 + 1);
  44.         __m128i mm21 = _mm_load_si128(src2);
  45.         __m128i mm22 = _mm_load_si128(src2 + 1);
  46.        
  47.         __m128i mm1 = _mm_xor_si128(mm11, mm21);
  48.         __m128i mm2 = _mm_xor_si128(mm12, mm22);
  49.  
  50.         __m128i mm = _mm_or_si128(mm1, mm2);
  51.        
  52.         if (!_mm_testz_si128(mm, mm))
  53.             return 0;    
  54.     }
  55.     const size_t rem = (size - tail_n) % 32;
  56.     const char* tail_1 = (const char*)head_1 + n * 32;
  57.     const char* tail_2 = (const char*)head_2 + n * 32;
  58.     for (size_t i = 0; i < rem; i++, tail_1++, tail_2++)
  59.     {
  60.         if (*tail_1 != *tail_2)
  61.             return 0;  
  62.     }
  63.    
  64.     return 1;
  65. }
  66.  
  67. #ifdef _MSC_VER
  68.     #define ALIGN(x) __declspec(align(x))
  69.     #define ATTR
  70. #else
  71.     #define ALIGN(x) __attribute__((aligned(x)))
  72.     #define ATTR __attribute__((target("avx")))
  73. #endif
  74.  
  75. typedef __m128i Vec;
  76. ATTR int memcmp_aligned(const char* src_1, const char* src_2, int len)
  77. {
  78.     // Intrisincs òðåáóþò êîíñòàíòíûå óêàçàòåëè
  79.     const Vec* ptr1 = (const Vec*)src_1;
  80.     const Vec* ptr2 = (const Vec*)src_2;
  81.     for (int i = 0; i < len; i += 16, ptr1++, ptr2++)
  82.     {
  83.         // Çàãðóæàåì â XMM 128-áèòíûé ðåãèñòð äàííûìè, íà÷èíàþùèìèñÿ ñ óêàçàòåëÿ ptr1
  84.         Vec M1 = _mm_load_si128(ptr1);
  85.         Vec M2 = _mm_load_si128(ptr2);
  86.         // Ñ÷èòàåì ïîáèòîâûé xor äâóõ âåêòîðîâ
  87.         Vec MX = _mm_xor_si128(M1, M2);
  88.         // _mm_testz_si128(A, B) âîçâðàùàåò 1, åñëè (A & B) == 0
  89.         if (!_mm_testz_si128(MX, MX))
  90.         {
  91.             /* Ýòà ïðîâåðêà âûïîëíÿåòñÿ îäèí ðàç, ìîæíî íå çàìîðà÷èâàòüñÿ c SIMD
  92.                Õîòÿ ìîæíî ñäåëàòü ýòî èñïîëüçóÿ ôóíêöèè _mm_cmplt_epi16 è _mm_movemask_epi8
  93.             */
  94.             for (int a = 0; a < 16; a++)
  95.                 if (src_1[i + a] != src_2[i + a])
  96.                     return src_1[i + a] < src_2[i + a] ? -1 : 1;
  97.         }
  98.     }
  99.     return 0;
  100. }
  101.  
  102. typedef __m128i Vec;
  103. ATTR int memcmp_unaligned(const char* src_1, const char* src_2, int len)
  104. {
  105.     // Intrisincs òðåáóþò êîíñòàíòíûå óêàçàòåëè
  106.     const Vec* ptr1 = (const Vec*)src_1;
  107.     const Vec* ptr2 = (const Vec*)src_2;
  108.     for (int i = 0; i < len; i += 16, ptr1++, ptr2++)
  109.     {
  110.         // Çàãðóæàåì â XMM 128-áèòíûé ðåãèñòð äàííûìè, íà÷èíàþùèìèñÿ ñ óêàçàòåëÿ ptr1
  111.         // Óêàçàòåëè íå âûðîâíåíû - ïîýòîìó èñïîëüçóåì ñïåöèàëüíóþ ôóíêöèþ _mm_loadu - load unaligned
  112.         Vec M1 = _mm_loadu_si128(ptr1);
  113.         Vec M2 = _mm_loadu_si128(ptr2);
  114.         // Ñ÷èòàåì ïîáèòîâûé xor äâóõ âåêòîðîâ
  115.         Vec MX = _mm_xor_si128(M1, M2);
  116.         // _mm_testz_si128(A, B) âîçâðàùàåò 1, åñëè (A & B) == 0
  117.         if (!_mm_testz_si128(MX, MX))
  118.         {
  119.             /* Ýòà ïðîâåðêà âûïîëíÿåòñÿ îäèí ðàç, ìîæíî íå çàìîðà÷èâàòüñÿ c SIMD
  120.                Õîòÿ ìîæíî ñäåëàòü ýòî èñïîëüçóÿ ôóíêöèè _mm_cmplt_epi16 è _mm_movemask_epi8
  121.             */
  122.             for (int a = 0; a < 16; a++)
  123.                 if (src_1[i + a] != src_2[i + a])
  124.                     return src_1[i + a] < src_2[i + a] ? -1 : 1;
  125.         }
  126.     }
  127.     return 0;
  128. }
  129.  
  130.  
  131. typedef __m128i Vec;
  132. ATTR int memcmp_unaligned_unrolled(const char* src_1, const char* src_2, int len)
  133. {
  134.     // Intrisincs òðåáóþò êîíñòàíòíûå óêàçàòåëè
  135.     const Vec* ptr1 = (const Vec*)src_1;
  136.     const Vec* ptr2 = (const Vec*)src_2;
  137.     for (int i = 0; i < len; i += 32, ptr1 += 2, ptr2 += 2)
  138.     {
  139.         // Çàãðóæàåì â XMM 128-áèòíûé ðåãèñòð äàííûìè, íà÷èíàþùèìèñÿ ñ óêàçàòåëÿ ptr1
  140.         // Óêàçàòåëè íå âûðîâíåíû - ïîýòîìó èñïîëüçóåì ñïåöèàëüíóþ ôóíêöèþ _mm_loadu - load unaligned
  141.         Vec M11 = _mm_loadu_si128(ptr1);
  142.         Vec M12 = _mm_loadu_si128(ptr2);
  143.         Vec M21 = _mm_loadu_si128(ptr1 + 1);
  144.         Vec M22 = _mm_loadu_si128(ptr2 + 1);
  145.         // Ñ÷èòàåì ïîáèòîâûé xor äâóõ âåêòîðîâ
  146.         Vec MX1 = _mm_xor_si128(M11, M12);
  147.         Vec MX2 = _mm_xor_si128(M21, M22);
  148.         MX1 = _mm_or_si128(MX1, MX2);
  149.         // _mm_testz_si128(A, B) âîçâðàùàåò 1, åñëè (A & B) == 0
  150.         if (!_mm_testz_si128(MX1, MX1))
  151.         {
  152.             /* Ýòà ïðîâåðêà âûïîëíÿåòñÿ îäèí ðàç, ìîæíî íå çàìîðà÷èâàòüñÿ c SIMD
  153.                Õîòÿ ìîæíî ñäåëàòü ýòî èñïîëüçóÿ ôóíêöèè _mm_cmplt_epi16 è _mm_movemask_epi8
  154.             */
  155.             for (int a = 0; a < 32; a++)
  156.                 if (src_1[i + a] != src_2[i + a])
  157.                     return src_1[i + a] < src_2[i + a] ? -1 : 1;
  158.         }
  159.     }
  160.     return 0;
  161. }
  162.  
  163. int memcmp_fast(const char* src_1, const char* src_2, int len)
  164. {
  165.     int middle_len = len & (~31);
  166.     int result = memcmp_unaligned_unrolled(src_1, src_2, middle_len);
  167.     if (result != 0)
  168.         return result;
  169.     // Ñðàâíèâàåì õâîñò
  170.     src_1 += middle_len, src_2 += middle_len;
  171.     for (int i = 0; i < len - middle_len; i++, src_1++, src_2++)
  172.     {
  173.         if (*src_1 != *src_2)
  174.             return *src_1 < *src_2 ? -1 : 1;
  175.     }
  176.     return 0;
  177. }
  178.  
  179. typedef __m128i Vec;
  180. // Íóæíûå íàì êóñêè ñòðîêè íà÷èíàåòñÿ ñ àäðåñîâ [src_1] è [src_2 + offset_2]
  181. template <int offset_2>
  182. ATTR int memcmp_alignr(const char* src_1, const char* src_2, int len)
  183. {
  184.     if (len <= 0)
  185.         return 0;
  186.        
  187.     const Vec* ptr1 = (const Vec*)src_1;
  188.     const Vec* ptr2 = (const Vec*)src_2;
  189.     Vec A = _mm_load_si128(ptr2);
  190.     for (int i = 0; i < len; i += 32, ptr1 += 2, ptr2 += 2)
  191.     {
  192.         Vec M11 = _mm_load_si128(ptr1);
  193.         Vec M21 = _mm_load_si128(ptr1 + 1);
  194.        
  195.         Vec B = _mm_load_si128(ptr2 + 1);
  196.         Vec C = _mm_load_si128(ptr2 + 2);
  197.        
  198.         // alignr âû÷èñëÿåò çíà÷åíèå ((B << 128) | A) >> (8 * offset_2) è çàïèñûâàåò ìëàäøèå 128 áèò â ðåãèñòð
  199.         Vec M12 = _mm_alignr_epi8(B, A, offset_2);
  200.         Vec M22 = _mm_alignr_epi8(C, B, offset_2);
  201.         A = C;
  202.        
  203.         Vec MX1 = _mm_xor_si128(M11, M12);
  204.         Vec MX2 = _mm_xor_si128(M21, M22);
  205.         MX1 = _mm_or_si128(MX1, MX2);
  206.         if (!_mm_testz_si128(MX1, MX1))
  207.         {
  208.             for (int a = 0; a < 32; a++)
  209.                 if (src_1[i + a] != src_2[i + offset_2 + a])
  210.                     return src_1[i + a] < src_2[i + offset_2 + a] ? -1 : 1;
  211.         }
  212.     }
  213.     return 0;
  214. }
  215.  
  216. int memcmp_fast_alignr(const char* src_1, const char* src_2, int len)
  217. {
  218.     // Âûðàâíèâàåì ïåðâûé óêàçàòåëü
  219.     while (((uintptr_t)src_1 % 16) != 0 && len > 0)
  220.     {                                
  221.         if (*src_1 != *src_2)
  222.             return *src_1 < *src_2 ? -1 : 1;
  223.         src_1++, src_2++, len--;
  224.     }
  225.     uintptr_t ptr_value = (uintptr_t)src_2;
  226.     int offset = (ptr_value & 15);
  227.    
  228.     /* Ñðàâíèâàåì áîëüøóþ ÷àñòü äëèíû ñ ïîìîùüþ âûðîâíåííîé âåðñèè,
  229.         èñïîëüçóþùåé SSE/AVX */
  230.     int result = 0;
  231.     int middle_len = (len - 32 < 0 ? 0 : len - 32) & (~31);
  232.     switch (offset)
  233.     {
  234.         case 0:
  235.             result = memcmp_alignr<0>(src_1, (char*)(ptr_value & (~15)), middle_len); break;
  236.         case 1:
  237.             result = memcmp_alignr<1>(src_1, (char*)(ptr_value & (~15)), middle_len); break;
  238.         case 2:
  239.             result = memcmp_alignr<2>(src_1, (char*)(ptr_value & (~15)), middle_len); break;
  240.         case 3:
  241.             result = memcmp_alignr<3>(src_1, (char*)(ptr_value & (~15)), middle_len); break;
  242.         case 4:
  243.             result = memcmp_alignr<4>(src_1, (char*)(ptr_value & (~15)), middle_len); break;
  244.         case 5:
  245.             result = memcmp_alignr<5>(src_1, (char*)(ptr_value & (~15)), middle_len); break;
  246.         case 6:
  247.             result = memcmp_alignr<6>(src_1, (char*)(ptr_value & (~15)), middle_len); break;
  248.         case 7:
  249.             result = memcmp_alignr<7>(src_1, (char*)(ptr_value & (~15)), middle_len); break;
  250.         case 8:
  251.             result = memcmp_alignr<8>(src_1, (char*)(ptr_value & (~15)), middle_len); break;
  252.         case 9:
  253.             result = memcmp_alignr<9>(src_1, (char*)(ptr_value & (~15)), middle_len); break;
  254.         case 10:
  255.             result = memcmp_alignr<10>(src_1, (char*)(ptr_value & (~15)), middle_len); break;
  256.         case 11:
  257.             result = memcmp_alignr<11>(src_1, (char*)(ptr_value & (~15)), middle_len); break;
  258.         case 12:
  259.             result = memcmp_alignr<12>(src_1, (char*)(ptr_value & (~15)), middle_len); break;
  260.         case 13:
  261.             result = memcmp_alignr<13>(src_1, (char*)(ptr_value & (~15)), middle_len); break;
  262.         case 14:
  263.             result = memcmp_alignr<14>(src_1, (char*)(ptr_value & (~15)), middle_len); break;
  264.         case 15:
  265.             result = memcmp_alignr<15>(src_1, (char*)(ptr_value & (~15)), middle_len); break;
  266.     }
  267.     if (result != 0)
  268.         return result;
  269.     // Ñðàâíèâàåì õâîñò
  270.     src_1 += middle_len, src_2 += middle_len;
  271.     for (int i = 0; i < len - middle_len; i++, src_1++, src_2++)
  272.     {
  273.         if (*src_1 != *src_2)
  274.             return *src_1 < *src_2 ? -1 : 1;
  275.     }
  276.     return 0;
  277. }
  278.  
  279.  
  280. int readInt(int &pos)
  281. {
  282.     int value = 0;
  283.     while (str[pos] > 32 && str[pos] < 64)
  284.     {
  285.         value *= 10;
  286.         value += str[pos] - '0';
  287.         pos++;
  288.     }
  289.     return value;
  290. }
  291.  
  292. int main()
  293. {
  294.     int shift = 0;
  295.     while (gets(str + shift))
  296.         shift += strlen(str + shift);
  297.  
  298.     int len = 0;
  299.     while (!isdigit(str[len])) len++;
  300.  
  301.     for (int i = 0; i < len; i++)
  302.         rStr[len - i - 1] = str[i];
  303.  
  304.     int pos = len;
  305.     int q = readInt(pos);
  306.  
  307.     int rIt = 0;
  308.     for (int i = 0; i < q; i++)
  309.     {                
  310.         if (str[pos] == 'p')
  311.         {                
  312.             pos += 12;
  313.             int l = readInt(pos);
  314.             pos++;
  315.             int r = readInt(pos);
  316.             l--, r--;
  317.            
  318.             if (memcmp_fast(str + l, rStr + (len - r - 1), (r - l + 1) / 2) == 0)
  319.             {
  320.                 strcpy(result + rIt, "Yes\n");
  321.                 rIt += 4;
  322.             }
  323.             else
  324.             {
  325.                 strcpy(result + rIt, "No\n");
  326.                 rIt += 3;
  327.             }
  328.         }
  329.         else
  330.         {              
  331.             pos += 7;
  332.             int x = readInt(pos);
  333.             pos++;
  334.             char c = str[pos++];
  335.             x--;
  336.             str[x] = c;
  337.             rStr[len - x - 1] = c;
  338.         }
  339.     }
  340.     puts(result);
  341.     return 0;
  342. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement