Submission #62353

#	Time	Username	Problem	Language	Result	Execution time	Memory
62353		kingpig9	Match (CEOI16_match)	C++11	100 / 100	25 ms	12732 KiB

match

//This is so hard to understand why it even works...
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5 + 10;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

int N;
char S[MAXN];
char ans[MAXN];
int prv[MAXN][26];

void rec (int lt, int rt) {
	if (lt > rt) {
		return;
	}

	int match = prv[rt][S[lt] - 'a'];	//which index you match with?
	if (match <= lt) {
		//then cannot match
		puts("-1");
		exit(0);
	}
	ans[lt] = '(';
	ans[match] = ')';
	rec(lt + 1, match - 1);
	rec(match + 1, rt);
}

int main() {
	if (fopen("match.in", "r")) {
		freopen("match.in", "r", stdin);
		freopen("match.out", "w", stdout);
	}
	scanf("%s", S);
	N = strlen(S);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 26; j++) {
			prv[i][j] = -1;
			if (j == S[i] - 'a') {
				prv[i][j] = i;
			} else if (i) {
				if (prv[i - 1][S[i] - 'a'] > 0) {
					prv[i][j] = prv[prv[i - 1][S[i] - 'a'] - 1][j];
				}
			}
		}
	}
	rec(0, N - 1);
	puts(ans);
}

Compilation message (stderr)

match.cpp: In function 'int main()':
match.cpp:41:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("match.in", "r", stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
match.cpp:42:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("match.out", "w", stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
match.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", S);
  ~~~~~^~~~~~~~~

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