Submission #406411

#	Time	Username	Problem	Language	Result	Execution time	Memory
406411		AriaH	Match (CEOI16_match)	C++11	100 / 100	73 ms	103388 KiB

match

/** 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 (stderr)

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 63 / 63