oj.uz

Submission #406411

# Submission time Handle Problem Language Result Execution time Memory
406411 2021-05-17T14:43:18 Z AriaH Match (CEOI16_match) C++11
100 / 100
 73 ms 103388 KB 
/** I can do this all day **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;
const int sigma = 26;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

char s[N], ans[N];

int n, last[sigma][N];

int solve(int l, int r)
{
	if(l > r) return 1;
	if((r - l + 1) & 1) return 0;
	int match = last[s[l] - 'a'][r];
	if(match <= l) return 0;
	ans[l] = '(', ans[match] = ')';
	return min(solve(l + 1, match - 1), solve(match + 1, r));
}

int main()
{
	scanf("%s", s);
	n = strlen(s);
	memset(last, -1, sizeof last);
	for(int i = 0; i < n; i ++)
	{
		int ch = s[i] - 'a';
		last[ch][i] = i;
		for(int j = 0; j < sigma; j ++)
		{
			if(j == ch) continue;
			if(i && last[ch][i - 1] > 0) last[j][i] = last[j][last[ch][i - 1] - 1];
		}
		
	}
	if(solve(0, n - 1) == 0) return !printf("-1");
	for(int i = 0; i < n; i ++) printf("%c", ans[i]);
	return 0;
}

/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message

match.cpp: In function 'int main()':
match.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |  scanf("%s", s);
      |  ~~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 102012 KB Output is correct
2 Correct 47 ms 102000 KB Output is correct
3 Correct 46 ms 102044 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 102012 KB Output is correct
2 Correct 47 ms 102000 KB Output is correct
3 Correct 46 ms 102044 KB Output is correct
4 Correct 47 ms 101968 KB Output is correct
5 Correct 48 ms 102028 KB Output is correct
6 Correct 54 ms 102092 KB Output is correct
7 Correct 53 ms 102016 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 102012 KB Output is correct
2 Correct 47 ms 102000 KB Output is correct
3 Correct 46 ms 102044 KB Output is correct
4 Correct 47 ms 101968 KB Output is correct
5 Correct 48 ms 102028 KB Output is correct
6 Correct 54 ms 102092 KB Output is correct
7 Correct 53 ms 102016 KB Output is correct
8 Correct 49 ms 101956 KB Output is correct
9 Correct 48 ms 102084 KB Output is correct
10 Correct 49 ms 102108 KB Output is correct
11 Correct 48 ms 102088 KB Output is correct
12 Correct 58 ms 102732 KB Output is correct
13 Correct 58 ms 102744 KB Output is correct
14 Correct 60 ms 103084 KB Output is correct
15 Correct 58 ms 103272 KB Output is correct
16 Correct 57 ms 103344 KB Output is correct
17 Correct 59 ms 103364 KB Output is correct
18 Correct 66 ms 102732 KB Output is correct
19 Correct 60 ms 103092 KB Output is correct
20 Correct 64 ms 102940 KB Output is correct
21 Correct 73 ms 103388 KB Output is correct