Submission #42443

#	Time	Username	Problem	Language	Result	Execution time	Memory
42443		nonocut	Popeala (CEOI16_popeala)	C++14	0 / 100	3 ms	912 KiB

popeala

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;
struct node {
    int cnt[26];
    node() {
        for(int i=0;i<26;i++) cnt[i] = 0;
    }
    bool operator < (node a) const {
        for(int i=0;i<26;i++) {
            if(a.cnt[i]!=cnt[i]) return a.cnt[i]<cnt[i];
        }
        return 0;
    }
};
int n;
char s[maxn], a[maxn], ans[maxn];
node val[maxn];
map<node, set<int>> pos[26];
void solve(int l, int r) {
    if(l>r) return ;
    int x = *(--pos[s[l]-'a'][val[l-1]].upper_bound(r));
//    printf("solve %d %d => x = %d\n",l,r,x);
    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++) {
        val[i] = val[i-1];
        a[++r] = s[i]-'a';
        val[i].cnt[s[i]-'a']++;
        while(r>=2 && a[r]==a[r-1]) {
            val[i].cnt[a[r]]-=2;
            r-=2;
        }
        pos[s[i]-'a'][val[i]].insert(i);
//        printf("i = %d (%c) : val = ",i,s[i]);
//        for(int j=0;j<5;j++) printf("%d",val[i].cnt[j]);
//        printf("\n");
	}
	if(r>0) return !printf("-1");
    solve(0,n-1);
    printf("%s",ans);
}

Compilation message (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:36:28: warning: array subscript has type 'char' [-Wchar-subscripts]
             val[i].cnt[a[r]]-=2;
                            ^
popeala.cpp:28:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %s",s);
                ^

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74