Submission #3790

#	Time	Username	Problem	Language	Result	Execution time	Memory
3790		blmarket	Make superpalindrome! (kriii1_M)	C++98	0 / 1	0 ms	2628 KiB

M

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <numeric>
#include <iterator>
#include <queue>
#include <set>
#include <map>
#include <vector>

#define mp make_pair
#define pb push_back
#define sqr(x) ((x)*(x))
#define foreach(it,c) for(typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;

template<typename T> int size(const T &a) { return a.size(); } 

char str[120000];
int L;

vector<int> pos(1,0);
int mincor = -1;

void go(int a) {
    int mymin = -1;
    vector<int> cur = pos;
    if(a&1) { // have center
        char c = str[pos[0] + (a/2)];
        for(int i=1;i<size(pos);i++) {
            char t = str[pos[i] + (a/2)];
            if(t == c) continue;
            if(t < c) { 
                mymin = pos[i] + (a/2);
                break;
            }
            if(t > c) {
                mymin = pos[0] + (a/2);
                break;
            }
        }
    }
    if(mymin != -1) {
        if(mincor == -1 || mincor > mymin) mincor = mymin;
    }
    if(a == 1) return;
    // split.
    int ll = size(pos);
    for(int i=0;i<ll;i++) {
        pos.pb(pos[i] + (a+1)/2);
    }
    go(a/2);

    char ff = str[cur[0] + (a/2)];
    if(cur[0] + (a/2) == mincor) {
        ff++;
    }
    for(int i=0;i<size(cur);i++) {
        int pp = cur[i] + (a/2);
        str[pp] = ff;
    }
}

int main(void)
{
    scanf(" %s", str);
    L = strlen(str);
//    cout << str << endl;
//    cout << L << endl;

    go(L);

    cout << str << endl;
}

• Subtask 1: 0 / 1