Submission #1007348


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

vector<int> suffix_array(const string &s){
    const int n=s.size();
    vector<int> rank(n+1),sa(n+1),tmp(n+1);
    for(int i=0; i<=n; ++i){
        sa[i]=i;
        rank[i]=i<n?s[i]:-1;
    }
    for(int k=1; k<=n; k*=2){
        auto compare=[&](int i,int j){
            if(rank[i]!=rank[j]) return rank[i]<rank[j];
            else{
                int ri=i+k<=n?rank[i+k]:-1;
                int rj=j+k<=n?rank[j+k]:-1;
                return ri<rj;
            }
        };
        sort(sa.begin(),sa.end(),compare);
        tmp[sa[0]]=0;
        for(int i=1; i<=n; ++i){
            tmp[sa[i]]=tmp[sa[i-1]]+(compare(sa[i-1],sa[i])?1:0);
        }
        for(int i=0; i<=n; ++i){
            rank[i]=tmp[i];
        }
    }
    return sa;
}

void solve(){
    int k;
    string s;
    cin >> k >> s;
    vector<int> sa=suffix_array(s),rank(s.size()+1);
    rep(i,0,s.size()+1) rank[sa[i]]=i;

    int l=(s.size()+k)/(k+1);
    auto ok=[&](int x){
        int count=0;
        for(int i=0; i<s.size();){
            if(rank[i]<=x) i+=l;
            else{
                if(l-1==0) return false;
                i+=l-1;
            }
            ++count;
        }
        return count<=k+1;
    };

    int lb=0,ub=s.size();
    while(ub-lb>1){
        int m=(lb+ub)/2;
        if(ok(m)) ub=m;
        else lb=m;
    }
    cout << s.substr(sa[ub],l) << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}

Submission Info

Submission Time
Task B - Problem where Commas Separate Digits
User walkre
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 2141 Byte
Status AC
Exec Time 84 ms
Memory 1616 KB

Judge Result

Set Name Sample Dataset1 Dataset2 Dataset3 Dataset4 Dataset5
Score / Max Score 0 / 0 100 / 100 100 / 100 200 / 200 200 / 200 400 / 400
Status
AC × 3
AC × 17
AC × 32
AC × 49
AC × 64
AC × 79
Set Name Test Cases
Sample subtask_02_ex1.txt, subtask_03_ex2.txt, subtask_03_ex3.txt
Dataset1 subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt
Dataset2 subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt
Dataset3 subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_06.txt, subtask_03_07.txt, subtask_03_08.txt, subtask_03_09.txt, subtask_03_10.txt, subtask_03_11.txt, subtask_03_12.txt, subtask_03_13.txt, subtask_03_14.txt, subtask_03_15.txt, subtask_03_ex2.txt, subtask_03_ex3.txt
Dataset4 subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_06.txt, subtask_03_07.txt, subtask_03_08.txt, subtask_03_09.txt, subtask_03_10.txt, subtask_03_11.txt, subtask_03_12.txt, subtask_03_13.txt, subtask_03_14.txt, subtask_03_15.txt, subtask_03_ex2.txt, subtask_03_ex3.txt, subtask_04_01.txt, subtask_04_02.txt, subtask_04_03.txt, subtask_04_04.txt, subtask_04_05.txt, subtask_04_06.txt, subtask_04_07.txt, subtask_04_08.txt, subtask_04_09.txt, subtask_04_10.txt, subtask_04_11.txt, subtask_04_12.txt, subtask_04_13.txt, subtask_04_14.txt, subtask_04_15.txt
Dataset5 subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_06.txt, subtask_03_07.txt, subtask_03_08.txt, subtask_03_09.txt, subtask_03_10.txt, subtask_03_11.txt, subtask_03_12.txt, subtask_03_13.txt, subtask_03_14.txt, subtask_03_15.txt, subtask_03_ex2.txt, subtask_03_ex3.txt, subtask_04_01.txt, subtask_04_02.txt, subtask_04_03.txt, subtask_04_04.txt, subtask_04_05.txt, subtask_04_06.txt, subtask_04_07.txt, subtask_04_08.txt, subtask_04_09.txt, subtask_04_10.txt, subtask_04_11.txt, subtask_04_12.txt, subtask_04_13.txt, subtask_04_14.txt, subtask_04_15.txt, subtask_05_01.txt, subtask_05_02.txt, subtask_05_03.txt, subtask_05_04.txt, subtask_05_05.txt, subtask_05_06.txt, subtask_05_07.txt, subtask_05_08.txt, subtask_05_09.txt, subtask_05_10.txt, subtask_05_11.txt, subtask_05_12.txt, subtask_05_13.txt, subtask_05_14.txt, subtask_05_15.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 3 ms 256 KB
subtask_01_02.txt AC 3 ms 256 KB
subtask_01_03.txt AC 3 ms 256 KB
subtask_01_04.txt AC 2 ms 256 KB
subtask_01_05.txt AC 3 ms 256 KB
subtask_01_06.txt AC 3 ms 256 KB
subtask_01_07.txt AC 3 ms 256 KB
subtask_01_08.txt AC 3 ms 256 KB
subtask_01_09.txt AC 3 ms 256 KB
subtask_01_10.txt AC 3 ms 256 KB
subtask_01_11.txt AC 3 ms 256 KB
subtask_01_12.txt AC 3 ms 256 KB
subtask_01_13.txt AC 3 ms 256 KB
subtask_01_14.txt AC 3 ms 256 KB
subtask_01_15.txt AC 3 ms 256 KB
subtask_01_16.txt AC 3 ms 256 KB
subtask_01_17.txt AC 3 ms 256 KB
subtask_02_01.txt AC 3 ms 256 KB
subtask_02_02.txt AC 3 ms 256 KB
subtask_02_03.txt AC 3 ms 256 KB
subtask_02_04.txt AC 3 ms 256 KB
subtask_02_05.txt AC 3 ms 256 KB
subtask_02_06.txt AC 3 ms 256 KB
subtask_02_07.txt AC 3 ms 256 KB
subtask_02_08.txt AC 3 ms 256 KB
subtask_02_09.txt AC 3 ms 256 KB
subtask_02_10.txt AC 3 ms 256 KB
subtask_02_11.txt AC 3 ms 256 KB
subtask_02_12.txt AC 3 ms 256 KB
subtask_02_13.txt AC 3 ms 256 KB
subtask_02_14.txt AC 3 ms 256 KB
subtask_02_ex1.txt AC 3 ms 256 KB
subtask_03_01.txt AC 3 ms 256 KB
subtask_03_02.txt AC 3 ms 256 KB
subtask_03_03.txt AC 3 ms 256 KB
subtask_03_04.txt AC 3 ms 256 KB
subtask_03_05.txt AC 3 ms 256 KB
subtask_03_06.txt AC 3 ms 256 KB
subtask_03_07.txt AC 3 ms 256 KB
subtask_03_08.txt AC 3 ms 256 KB
subtask_03_09.txt AC 3 ms 256 KB
subtask_03_10.txt AC 3 ms 256 KB
subtask_03_11.txt AC 3 ms 256 KB
subtask_03_12.txt AC 3 ms 256 KB
subtask_03_13.txt AC 3 ms 256 KB
subtask_03_14.txt AC 3 ms 256 KB
subtask_03_15.txt AC 2 ms 256 KB
subtask_03_ex2.txt AC 2 ms 256 KB
subtask_03_ex3.txt AC 3 ms 256 KB
subtask_04_01.txt AC 3 ms 256 KB
subtask_04_02.txt AC 3 ms 256 KB
subtask_04_03.txt AC 3 ms 256 KB
subtask_04_04.txt AC 3 ms 256 KB
subtask_04_05.txt AC 3 ms 256 KB
subtask_04_06.txt AC 3 ms 256 KB
subtask_04_07.txt AC 3 ms 256 KB
subtask_04_08.txt AC 3 ms 256 KB
subtask_04_09.txt AC 3 ms 256 KB
subtask_04_10.txt AC 3 ms 256 KB
subtask_04_11.txt AC 3 ms 256 KB
subtask_04_12.txt AC 3 ms 256 KB
subtask_04_13.txt AC 3 ms 256 KB
subtask_04_14.txt AC 3 ms 256 KB
subtask_04_15.txt AC 3 ms 256 KB
subtask_05_01.txt AC 83 ms 1616 KB
subtask_05_02.txt AC 84 ms 1616 KB
subtask_05_03.txt AC 82 ms 1616 KB
subtask_05_04.txt AC 82 ms 1616 KB
subtask_05_05.txt AC 82 ms 1616 KB
subtask_05_06.txt AC 82 ms 1616 KB
subtask_05_07.txt AC 82 ms 1616 KB
subtask_05_08.txt AC 81 ms 1616 KB
subtask_05_09.txt AC 82 ms 1616 KB
subtask_05_10.txt AC 84 ms 1616 KB
subtask_05_11.txt AC 79 ms 1616 KB
subtask_05_12.txt AC 71 ms 1616 KB
subtask_05_13.txt AC 56 ms 1280 KB
subtask_05_14.txt AC 74 ms 1536 KB
subtask_05_15.txt AC 29 ms 768 KB