oj.uz

Submission #62356

# Submission time Handle Problem Language Result Execution time Memory
62356 2018-07-28T08:35:41 Z kingpig9 Match (CEOI16_match) C++11
10 / 100
 3 ms 672 KB 
//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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 416 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Incorrect 2 ms 672 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Incorrect 2 ms 672 KB Output isn't correct
5 Halted 0 ms 0 KB -