Advertisement
Guest User

Untitled

a guest
Dec 16th, 2018
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.42 KB | None | 0 0
  1. /*
  2. ..... . . . .
  3. . . . . . . .
  4. . ..... . .....
  5. . . . . . .
  6. */
  7. #pragma GCC optimize("Ofast")
  8. #pragma GCC optimize("no-stack-protector")
  9. #pragma GCC optimize("unroll-loops")
  10. #pragma GCC optimize("fast-math")
  11. #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
  12. #include <iostream>
  13. #include <vector>
  14. #include <string>
  15. #include <algorithm>
  16. #include <cstdio>
  17. #include <numeric>
  18. #include <cstring>
  19. #include <ctime>
  20. #include <cstdlib>
  21. #include <set>
  22. #include <map>
  23. #include <unordered_map>
  24. #include <unordered_set>
  25. #include <list>
  26. #include <cmath>
  27. #include <bitset>
  28. #include <cassert>
  29. #include <queue>
  30. #include <stack>
  31. #include <deque>
  32. #include <cassert>
  33. #include <iomanip>
  34. #include <random>
  35. #include <sstream>
  36.  
  37. using namespace std;
  38.  
  39.  
  40.  
  41. #define prev prev228
  42. #define index index228
  43. #define left left228
  44. #define right right228
  45. #define hash hash228
  46. #define y1 y1228
  47.  
  48. template<typename T> void uin(T &a, T b) {
  49. if (b < a) a = b;
  50. }
  51.  
  52. template<typename T> void uax(T &a, T b) {
  53. if (b > a) a = b;
  54. }
  55.  
  56. const int maxDO = 2097152 + 228, INF = 1e9 + 228;
  57.  
  58. const int maxn = 1000 * 1000 + 228;
  59.  
  60. struct node
  61. {
  62. int mn;
  63. int mod;
  64. int l, r;
  65. node() {
  66. mn = mod = l = r = 0;
  67. }
  68. };
  69.  
  70. node d[maxDO];
  71.  
  72. void build(int l, int r, int v = 1) {
  73. d[v].l = l;
  74. d[v].r = r;
  75. if (l == r) return;
  76. int m = (l + r) >> 1;
  77. build(l, m, v << 1);
  78. build(m + 1, r, v << 1 | 1);
  79. }
  80.  
  81. int gets(int v) {
  82. return d[v].mn + d[v].mod;
  83. }
  84.  
  85. void push(int v) {
  86. d[v << 1].mod += d[v].mod;
  87. d[v << 1 | 1].mod += d[v].mod;
  88. d[v].mod = 0;
  89. d[v].mn = min(gets(v << 1), gets(v << 1 | 1));
  90. }
  91.  
  92. void update(int l, int r, int x, int v = 1) {
  93. if (l > r || d[v].l > r || d[v].r < l) return ;
  94. if (l <= d[v].l && d[v].r <= r) {
  95. d[v].mod += x;
  96. } else {
  97. push(v);
  98. update(l, r, x, v << 1);
  99. update(l, r, x, v << 1 | 1);
  100. d[v].mn = min(gets(v << 1), gets(v << 1 | 1));
  101. }
  102. }
  103.  
  104. int get(int l, int r, int v = 1) {
  105. if (l > r || d[v].l > r || d[v].r < l) return INF;
  106. if (l <= d[v].l && d[v].r <= r) return gets(v);
  107. push(v);
  108. return min(get(l, r, v << 1), get(l, r, v << 1 | 1));
  109. }
  110.  
  111. int bal[maxn];
  112.  
  113. signed main() {
  114. ios_base::sync_with_stdio(false);
  115. cin.tie(0);
  116. string s;
  117. cin >> s;
  118. int n = (int)s.size();
  119. for (int i = 1; i <= n; ++i) {
  120. bal[i] = bal[i - 1];
  121. if (s[i - 1] == '(') ++bal[i];
  122. else --bal[i];
  123. }
  124. bool ok1 = 1, ok2 = 1;
  125. for (int i = 0; i < n; ++i) {
  126. if (s[i] != ')') ok1 = 0;
  127. if (s[i] == '(') ok2 = 0;
  128. }
  129. if (ok1 || ok2) {
  130. if (ok1) {
  131. for (int i = 0; i < n; ++i) {
  132. s += ')';
  133. }
  134. cout << s << endl;
  135. } else {
  136. for (int i = 0; i < n; ++i) {
  137. cout << '(';
  138. }
  139. cout << s << endl;
  140. }
  141. return 0;
  142. }
  143. build(1, n + n);
  144. for (int i = 1; i <= n; ++i) {
  145. update(i, i, bal[i]);
  146. }
  147. int ans = INF;
  148. int shft = 0;
  149. int addb = 0, adde = 0;
  150. for (int shift = 0; shift < n; ++shift) {
  151. int len = n;
  152. int minbal = get(1, n);
  153. int add_begin = max(0, -minbal);
  154. int add_end = get(n + shift, n + shift) + add_begin;
  155. cout << "shift=" << shift << " add_begin=" << add_begin << " add_end=" << add_end << endl;
  156. if (n + add_begin + add_end < ans) {
  157. ans = n + add_begin + add_end;
  158. shft = shift;
  159. addb = add_begin;
  160. adde = add_end;
  161.  
  162. }
  163.  
  164. if (n + add_begin + add_end == ans) {
  165. for (int i = 0; i < n; ++i) {
  166. if (s[shift + i] < s[shft + i]) {
  167. shft = shift;
  168. addb = add_begin;
  169. adde = add_end;
  170. break;
  171. }
  172. if (s[shift + i] > s[shft + i]) {
  173. break;
  174. }
  175. }
  176. }
  177. if (s[shift] == '(') {
  178. update(1, n - 1, -1);
  179. } else {
  180. update(1, n - 1, 1);
  181. }
  182. }
  183. for (int i = 0; i < addb; ++i) {
  184. cout << '(';
  185. }
  186. for (int i = 0; i < n; ++i) {
  187. cout << s[(shft + i) % n];
  188. }
  189. for (int i = 0; i < adde; ++i) {
  190. cout << ')';
  191. }
  192. cout << endl;
  193. return 0;
  194. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement