Submission #3746

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3746	2013-08-31T08:05:10 Z	wookayin	Make superpalindrome! (kriii1_M)	C++	1 / 1	52 ms	15348 KB

M

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
 
 
using namespace std;
 
int n;
char dat[100003];
 
vector<int> graph[100003];
int v[100003];
int grp[100003];
 
vector<int> group[100003];
char groupC[100003];
int totalGroups;
 
void cons(int s, int e) {
    if (s == e || s + 1 == e) {
                return;
        }
        int m = (s+e)/2;
        if ((s+e)%2 == 0) { // even length
                cons(s,m);
                cons(m,e);
        } else {
                cons(s,m);
                cons(m+1,e);
        }
        for(int i = s; i < m; i++) {
                graph[i].push_back(e-(i-s)-1);
        }
}
 
void dfs(int nod)
{
        v[nod] = 1;
        grp[nod] = totalGroups;
        group[totalGroups].push_back(nod);
        for(int i = 0; i < graph[nod].size();i ++){
                int next = graph[nod][i];
                if (v[next]) continue;
                dfs(next);
        }
}
 
char result[100003];
 
int main()
{
        scanf("%s",dat);
        n = strlen(dat);
        cons(0, n);
        int bad = n;
        for(int i = 0; i < n; i++) {
                if (v[i]) continue;
                dfs(i);
                totalGroups++;
        }
        for(int i = 0; i < totalGroups;i ++) {
                sort(group[i].begin(), group[i].end());
                char value = dat[group[i][0]];
                groupC[i] = value;
                for(int j = 1; j < group[i].size(); j++){
                        if( value != dat[group[i][j]]) {
                                bad = min(bad,group[i][j]);
                        }
                }
        }
        if (groupC[grp[bad]] > dat[bad]) {
                for(int i = totalGroups - 1; i >= 0; i--) {
                        if(group[i][0] > bad) {
                                groupC[i] = 'a';
                        }
                }
        } else {
                for(int i = totalGroups - 1; i >= 0; i--) {
                        if(groupC[i] == 'z' || group[i][0] > bad) {
                                groupC[i] = 'a';
                        } else {
                                groupC[i] ++;
                                break;
                        }
                }
        }
        for(int i = 0; i < n; i++) {
                result[i] = groupC[grp[i]];
        }
 
        printf("%s\n",result);
        return 0;
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	14780 KB	Output is correct
2	Correct	52 ms	14844 KB	Output is correct
3	Correct	36 ms	14560 KB	Output is correct
4	Correct	48 ms	14856 KB	Output is correct
5	Correct	44 ms	14824 KB	Output is correct
6	Correct	0 ms	6972 KB	Output is correct
7	Correct	0 ms	7640 KB	Output is correct
8	Correct	0 ms	7640 KB	Output is correct
9	Correct	0 ms	6972 KB	Output is correct
10	Correct	44 ms	14664 KB	Output is correct
11	Correct	32 ms	14748 KB	Output is correct
12	Correct	48 ms	14820 KB	Output is correct
13	Correct	48 ms	15348 KB	Output is correct
14	Correct	44 ms	14748 KB	Output is correct
15	Correct	48 ms	14476 KB	Output is correct
16	Correct	28 ms	11580 KB	Output is correct
17	Correct	32 ms	11576 KB	Output is correct
18	Correct	28 ms	11580 KB	Output is correct
19	Correct	48 ms	14620 KB	Output is correct
20	Correct	24 ms	11580 KB	Output is correct