답안 #3746

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
3746 2013-08-31T08:05:10 Z wookayin Make superpalindrome! (kriii1_M) C++
1 / 1
52 ms 15348 KB
#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;
}
# 결과 실행 시간 메모리 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