Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ..... . . . .
- . . . . . . .
- . ..... . .....
- . . . . . .
- */
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("no-stack-protector")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC optimize("fast-math")
- #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
- #include <iostream>
- #include <vector>
- #include <string>
- #include <algorithm>
- #include <cstdio>
- #include <numeric>
- #include <cstring>
- #include <ctime>
- #include <cstdlib>
- #include <set>
- #include <map>
- #include <unordered_map>
- #include <unordered_set>
- #include <list>
- #include <cmath>
- #include <bitset>
- #include <cassert>
- #include <queue>
- #include <stack>
- #include <deque>
- #include <cassert>
- #include <iomanip>
- #include <random>
- #include <sstream>
- using namespace std;
- #define prev prev228
- #define index index228
- #define left left228
- #define right right228
- #define hash hash228
- #define y1 y1228
- template<typename T> void uin(T &a, T b) {
- if (b < a) a = b;
- }
- template<typename T> void uax(T &a, T b) {
- if (b > a) a = b;
- }
- const int maxDO = 2097152 + 228, INF = 1e9 + 228;
- const int maxn = 1000 * 1000 + 228;
- struct node
- {
- int mn;
- int mod;
- int l, r;
- node() {
- mn = mod = l = r = 0;
- }
- };
- node d[maxDO];
- void build(int l, int r, int v = 1) {
- d[v].l = l;
- d[v].r = r;
- if (l == r) return;
- int m = (l + r) >> 1;
- build(l, m, v << 1);
- build(m + 1, r, v << 1 | 1);
- }
- int gets(int v) {
- return d[v].mn + d[v].mod;
- }
- void push(int v) {
- d[v << 1].mod += d[v].mod;
- d[v << 1 | 1].mod += d[v].mod;
- d[v].mod = 0;
- d[v].mn = min(gets(v << 1), gets(v << 1 | 1));
- }
- void update(int l, int r, int x, int v = 1) {
- if (l > r || d[v].l > r || d[v].r < l) return ;
- if (l <= d[v].l && d[v].r <= r) {
- d[v].mod += x;
- } else {
- push(v);
- update(l, r, x, v << 1);
- update(l, r, x, v << 1 | 1);
- d[v].mn = min(gets(v << 1), gets(v << 1 | 1));
- }
- }
- int get(int l, int r, int v = 1) {
- if (l > r || d[v].l > r || d[v].r < l) return INF;
- if (l <= d[v].l && d[v].r <= r) return gets(v);
- push(v);
- return min(get(l, r, v << 1), get(l, r, v << 1 | 1));
- }
- int bal[maxn];
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- string s;
- cin >> s;
- int n = (int)s.size();
- for (int i = 1; i <= n; ++i) {
- bal[i] = bal[i - 1];
- if (s[i - 1] == '(') ++bal[i];
- else --bal[i];
- }
- bool ok1 = 1, ok2 = 1;
- for (int i = 0; i < n; ++i) {
- if (s[i] != ')') ok1 = 0;
- if (s[i] == '(') ok2 = 0;
- }
- if (ok1 || ok2) {
- if (ok1) {
- for (int i = 0; i < n; ++i) {
- s += ')';
- }
- cout << s << endl;
- } else {
- for (int i = 0; i < n; ++i) {
- cout << '(';
- }
- cout << s << endl;
- }
- return 0;
- }
- build(1, n + n);
- for (int i = 1; i <= n; ++i) {
- update(i, i, bal[i]);
- }
- int ans = INF;
- int shft = 0;
- int addb = 0, adde = 0;
- for (int shift = 0; shift < n; ++shift) {
- int len = n;
- int minbal = get(1, n);
- int add_begin = max(0, -minbal);
- int add_end = get(n + shift, n + shift) + add_begin;
- cout << "shift=" << shift << " add_begin=" << add_begin << " add_end=" << add_end << endl;
- if (n + add_begin + add_end < ans) {
- ans = n + add_begin + add_end;
- shft = shift;
- addb = add_begin;
- adde = add_end;
- }
- if (n + add_begin + add_end == ans) {
- for (int i = 0; i < n; ++i) {
- if (s[shift + i] < s[shft + i]) {
- shft = shift;
- addb = add_begin;
- adde = add_end;
- break;
- }
- if (s[shift + i] > s[shft + i]) {
- break;
- }
- }
- }
- if (s[shift] == '(') {
- update(1, n - 1, -1);
- } else {
- update(1, n - 1, 1);
- }
- }
- for (int i = 0; i < addb; ++i) {
- cout << '(';
- }
- for (int i = 0; i < n; ++i) {
- cout << s[(shft + i) % n];
- }
- for (int i = 0; i < adde; ++i) {
- cout << ')';
- }
- cout << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement