mrlolthe1st

Untitled

Sep 23rd, 2021
811
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #pragma GCC Optimize("Ofast")
  3. #include <iostream>
  4. #include <vector>
  5. #include <set>
  6. #include <string>
  7. #include <time.h>
  8. #include <unordered_set>
  9. #include <map>
  10. #include <queue>
  11. #include <algorithm>
  12. #include <fstream>
  13. #include <cstddef>
  14. #include <cstdio>
  15. #include <iostream>
  16. #include <memory>
  17. #include <stdexcept>
  18. #include <string>
  19. #include <array>
  20. using namespace std;
  21.  
  22. #define vi vector<int>
  23. #define vec vector
  24. char open[256] = {}, close[256] = {};
  25. int go(string s) {
  26.  
  27.     vec<char> st;
  28.     deque<char> cur;
  29.     vec<int> st2;
  30.     string res;
  31.     int x = 0, ans = 0;
  32.     // Особо не отличается от проверки на правильность
  33.     for (int i = 0; i < s.length(); ++i) {
  34.         if (open[s[i]]) {
  35.             cur.push_back(s[i]);
  36.             st2.push_back(x);
  37.             x = 0;
  38.             st.push_back(close[s[i]]);
  39.         }
  40.         else {
  41.             if (st.size() && st.back() == s[i]) {
  42.                 cur.push_back(s[i]);
  43.                 st.pop_back();
  44.                 x = st2.back();
  45.                 ++x;
  46.                 st2.pop_back();
  47.                 ans += x;
  48.             }
  49.             else {
  50.                 while (st.size()) cur.pop_front(), st.pop_back(), st2.pop_back();
  51.                 x = 0;
  52.                 if (res.size() < cur.size())
  53.                 {
  54.                     res = "";
  55.                     for (auto& e : cur)
  56.                         res += e;
  57.                 }
  58.                 cur.clear();
  59.             }
  60.         }
  61.     }
  62.     //if (!st.size())++ans;
  63.     while (st.size()) cur.pop_back(), st.pop_back(), ans += st2.back() + 1, st2.pop_back();
  64.     if (res.size() < cur.size())
  65.     {
  66.         res = "";
  67.         for (auto& e : cur)
  68.             res += e;
  69.     }
  70.     return ans;
  71. }
  72.  
  73. int go2(string s) {
  74.     int n = s.length();
  75.     int ans = 0;
  76.     for (int i = 0; i < n; ++i) {
  77.         vec<char> st;
  78.         int ok = 1;
  79.         for (int j = i; j < n; ++j) {
  80.             if (open[s[j]]) {
  81.                 st.push_back(close[s[j]]);
  82.             }
  83.             else {
  84.                 if (st.size() && st.back() == s[j]) {
  85.                     st.pop_back();
  86.                 }
  87.                 else {
  88.                     ok = 0; break;
  89.                 }
  90.             }
  91.             if (!st.size() && ok) ans++;
  92.         }
  93.     }
  94.     return ans;
  95. }
  96.  
  97. int main() {
  98.     open['['] = 1;
  99.     open['{'] = 1;
  100.     open['('] = 1;
  101.     close['['] = ']';
  102.     close['('] = ')';
  103.     close['{'] = '}';
  104.     go2("{}");
  105.     int n = 60;
  106.     for (int i = 0; i < 10000; ++i) {
  107.         string s;
  108.         for (int j = 0; j < n; ++j)
  109.             s += ("([{}])"[rand() % 6]);
  110.         int a = go(s), b = go2(s);
  111.         if (a != b) {
  112.             cout << "!"; go2(s);
  113.         }
  114.     }
  115. }
RAW Paste Data