oj.uz

Submission #42442

# Submission time Handle Problem Language Result Execution time Memory
42442 2018-02-27T07:45:14 Z nonocut Match (CEOI16_match) C++14
10 / 100
 2000 ms 3312 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 5;
int n;
char s[maxn], a[maxn], ans[maxn];
int val[maxn];
set<int> pos[30][maxn];
void solve(int l, int r) {
//    printf("solve %d %d\n",l,r);
    if(l>r) return ;
    int x = *(--pos[s[l]-'a'][val[l-1]].upper_bound(r));
    ans[l] = '('; ans[x] = ')';
    solve(l+1,x-1); solve(x+1,r);
}
int main() {
	scanf(" %s",s);
	n = strlen(s);
	int r = 0;
	for(int i=0;i<n;i++) {
        a[++r] = s[i];
        while(r>=2 && a[r]==a[r-1]) r-=2;
        val[i] = r;
        pos[s[i]-'a'][val[i]].insert(i);
	}
	if(r>0) return !printf("-1");
    solve(0,n-1);
    printf("%s",ans);
}

Compilation message

match.cpp: In function 'int main()':
match.cpp:16:16: 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 4 ms 3192 KB Output is correct
2 Correct 4 ms 3192 KB Output is correct
3 Correct 3 ms 3240 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3192 KB Output is correct
2 Correct 4 ms 3192 KB Output is correct
3 Correct 3 ms 3240 KB Output is correct
4 Execution timed out 2033 ms 3312 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3192 KB Output is correct
2 Correct 4 ms 3192 KB Output is correct
3 Correct 3 ms 3240 KB Output is correct
4 Execution timed out 2033 ms 3312 KB Time limit exceeded
5 Halted 0 ms 0 KB -