Submission #62356

#	Time	Username	Problem	Language	Result	Execution time	Memory
62356		kingpig9	Match (CEOI16_match)	C++11	10 / 100	3 ms	672 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))

void kill() {
	puts("-1");
	exit(0);
}

int N;
char S[MAXN];
char ans[MAXN];
int prv[MAXN][26][2];	//[pos][letter][parity]

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

	int match = prv[rt][S[lt] - 'a'][!(lt % 2)];	//which index you match with?
	if (match <= lt) {
		//then cannot match
		kill();
	}
	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);
	if (N % 2) {
		kill();
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 26; j++) {
			for (int k = 0; k < 2; k++) {
				prv[i][j][k] = (i ? prv[i - 1][j][k] : -1);
			}
			prv[i][S[i] - 'a'][i % 2] = i;
		}
	}
	rec(0, N - 1);
	puts(ans);
}

Compilation message (stderr)

match.cpp: In function 'int main()':
match.cpp:45: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:46: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:48: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: 0 / 27
• Subtask 3: 0 / 63