Submission #3721

#	Time	Username	Problem	Language	Result	Execution time	Memory
3721		wookayin	Make superpalindrome! (kriii1_M)	C++98	0 / 1	44 ms	14780 KiB

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]) {
        } 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: 0 / 1