Submission #2448203

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef complex<double> point;
#define mapii map<int, int>
#define debug(a) cout << #a << ": " << a << endl
#define debuga1(a, l, r) fto(i, l, r) cout << a[i] << " "; cout << endl
#define fdto(i, r, l) for(int i = (r); i >= (l); --i)
#define fto(i, l, r) for(int i = (l); i <= (r); ++i)
#define forit(it, var) for(__typeof(var.begin()) it = var.begin(); it != var.end(); it++)
#define forrit(rit, var) for(__typeof(var.rbegin()) rit = var.rbegin(); rit != var.rend(); rit++)
#define ii pair<int, int>
#define iii pair<int, ii>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define maxN 100005
#define maxK 20
#define MOD 1000
#define oo 1000000000000000007LL
#define sz(a) (int)a.size()

const double PI = acos(-1.0);

double fRand(double fMin, double fMax)
{
    double f = (double)rand() / RAND_MAX;
    return fMin + f * (fMax - fMin);
}

template <class T>
T min(T a, T b, T c) {
    return min(a, min(b, c));
}

template <class T>
T max(T a, T b, T c) {
    return max(a, max(b, c));
}

int k, n, l, sa[maxN], rnk[maxN], lcp[maxN], b[maxK][maxN];
char s[2*maxN];

void buildSA() {
    fto(i, 0, n-1) rnk[i] = s[i];
    int j = 0;
    while (true) {
        vector<pair<ii, int> > pos(n);
        fto(i, 0, n-1) pos[i] = mp(mp(rnk[i], rnk[i+(1<<j)]), i);
        sort(pos.begin(), pos.end());

        int cnt = 1;
        fto(i, 0, n-1) {
            if (i > 0 && pos[i-1].ff != pos[i].ff) ++cnt;
            rnk[pos[i].ss] = cnt;
        }
        if (cnt == n) break;

        ++j;
    }

    fto(i, 0, n-1) {
        --rnk[i];
        sa[rnk[i]] = i;
    }
}

void buildLCP() {
    int k = 0;
    fto(i, 0, n-1) {
        if (rnk[i] == 0) continue;
        k = max(0, k-1);
        int j = sa[rnk[i]-1];
        while (s[j+k] == s[i+k]) ++k;
        lcp[rnk[i]-1] = k;
    }
}

void buildTable() {
    fto(j, 0, n-2) b[0][j] = lcp[j];
    fto(i, 1, log2(n-1)) {
        fto(j, 0, n-(1<<i)-1) b[i][j] = min(b[i-1][j], b[i-1][j+(1<<(i-1))]);
    }
}

int getLCP(int x, int y) {
    int l = rnk[x], r = rnk[y];
    if (l > r) swap(l, r);
    --r;
    int i = log2(r-l+1);
    return min(b[i][l], b[i][r-(1<<i)+1]);
}

bool cmp(int i, int j) {
    if (i == j) return true;
    int k = getLCP(i, j);
    if (k >= l) return true;
    return (s[i+k] <= s[j+k]);
}

bool Check(int ind) {
    int i = 0, cnt = 0;
//    debug(ind);
    while (i < n) {
//        debug(i);
        if (n-i < l) i = n;
        else if (cmp(i, ind)) i += l;
        else if (l == 1) return false;
        else i += l-1;
        ++cnt;
    }
    return (cnt <= k+1);
}

int main () {
    scanf("%d%s", &k, s);
    n = strlen(s);

    l = (n+k)/(k+1);

    buildSA();
    buildLCP();
    buildTable();

//    fto(i, 0, n-1) printf("%d %d %d\n", sa[i], rnk[i], lcp[i]);

    vector<int> cand;
    fto(i, 0, n-1)
        if (sa[i] <= n-l) cand.pb(sa[i]);

    int lo = 0, hi = sz(cand)-1, res = -1;
    while (lo <= hi) {
        int mid = (lo+hi)/2;
        if (Check(cand[mid])) {
            res = cand[mid];
            hi = mid-1;
        } else lo = mid+1;
    }

    printf("%.*s", l, s+res);

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:119:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%s", &k, s);
                         ^

Judge Result