Submission #110860

#	Time	Username	Problem	Language	Result	Execution time	Memory
110860		mosesmayer	Match (CEOI16_match)	C++17	10 / 100	2 ms	512 KiB

match

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int mxsz = 1e5 + 5;

int n;
char S[mxsz], ans[mxsz];
int lft[mxsz][26];

void prec(){
	for (int i = 1, p; i <= n; i++){
		p = S[i] - 'a';
		for (int j = 0; j < 26; j++){
			lft[i][j] = lft[i-1][j];
		}
		lft[i][p] = i;
	}
	//for (int i = 1; i <= n; i++) for (int j = 0; j < 26; j++) cout << lft[i][j] << " \n"[j==25];
}
inline void CANNOT(){
	puts("-1"); exit(0);
}
void rec(int l, int r){
	//cout << l << ' ' << r << '\n';
	if (l > r) return;
	int pos = lft[r][S[l] - 'a'];
	if (pos <= l) CANNOT();
	ans[l] = '('; ans[pos] = ')';
	rec(l+1, pos - 1); rec(pos+1, r);
}
int main(){
	scanf("%s", S+1);
	n = strlen(S+1);
	ans[n+1] = '\0';
	prec();
	rec(1,n);
	puts(ans+1);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 63