CODE FESTIVAL 2016 Elimination Tournament Round 1 (Parallel)

Submission #1127770

Source codeソースコード

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

struct cww{cww(){
    ios::sync_with_stdio(false);cin.tie(0);
}}star;
#define fin "\n"
#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define fi first
#define se second
#define pb push_back
#define DEBUG if(0)
template <typename T>inline void chmin(T &l,T r){l=min(l,r);}
template <typename T>inline void chmax(T &l,T r){l=max(l,r);}
template <typename T>
istream& operator>>(istream &is,vector<T> &v){
    for(auto &it:v)is>>it;
    return is;
}

namespace SA {
    int n, k;
    int R[500000];
    int T[500000];
    bool compare_sa(int i, int j) {
        if (R[i] != R[j])return R[i] < R[j];
        else {
            int ri = i + k <= n ? R[i + k] : -1;
            int rj = j + k <= n ? R[j + k] : -1;
            return ri < rj;
        }
    }
    vector<int> construct_sa(string& S) {
        n = S.size();
        vector<int> sa(n + 1);
        for (int i = 0; i <= n; i++) {
            sa[i] = i;
            R[i] = i < n ? S[i] : -1;
        }
 
        for (k = 1; k <= n; k *= 2) {
            sort(sa.begin(), sa.end(), compare_sa);
            T[sa[0]] = 0;
            for (int i = 1; i <= n; i++) 
                T[sa[i]] = T[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
            for (int i = 0; i <= n; i++)
                R[i] = T[i];
        }
        return sa;
    }
    vector<int> construct_lcp(string& S, vector<int> &sa) {
        n = S.size();
        for (int i = 0; i <= n; i++)R[sa[i]] = i;
        int h = 0;
        vector<int> lcp(n + 1, 0);
        for (int i = 0; i < n; i++) {
            int j = sa[R[i] - 1];
            if (h > 0)h--;
            for (; j + h < n&&i + h < n; h++) {
                if (S[j + h] != S[i + h])break;
            }
            lcp[R[i] - 1] = h;
        }
        return lcp;
    }
}

const int INF=114514;

typedef int A;
struct node{
    A a;

};
A mg(node& v,int l,int r){
    return v.a;
}
A mg(A l,A r){
    return min(l,r);
}
namespace ST{
    node mem[1][2123456];
    int cnt=0;
    node* get(){return mem[cnt++];}
}
struct seg_tree{
    int size;
    node *seg;
    void init(int l,int r,vector<int> &lcp,int k=0){
        auto &v=seg[k];
        //flag関連の処理

        if(r-l==1){
            //葉の時の処理
            if(l>=lcp.size())v.a=INF;
            else v.a=lcp[l];
        }
        else if(r-l>1){
            int m=(l+r)/2;
            init(l,m,lcp,k*2+1);init(m,r,lcp,k*2+2);
            v.a=mg(mg(seg[k*2+1],l,m),mg(seg[k*2+2],m,r));
        }
    }
    seg_tree(int n,vector<int> &lcp){
        size=1;
        while(size<n)size*=2;
        seg=ST::get();
        init(0,size,lcp);
    }

#define LQ a,b,k*2+1,l,m
#define RQ a,b,k*2+2,m,r
    A get(int a,int b,int k,int l,int r){
        if(a<=l&&r<=b)return mg(seg[k],l,r);
        //push(k,l,r);          
        int m=(l+r)/2;
        bool ll=!(m<=a||b<=l);
        bool rr=!(r<=a||b<=m);
        A ret;
        if(ll&&rr)ret=mg(get(LQ),get(RQ));
        else if(ll)ret=get(LQ);
        else ret=get(RQ);
        seg[k].a=mg(mg(seg[k*2+1],l,m),mg(seg[k*2+2],m,r));
        return ret;
    }
    A get(int a,int b){return get(a,b,0,0,size);}
};
int main(){
    int K;string S;
    cin>>K>>S;
    int N=S.size();
    K++;
    int max_len=(N+K-1)/K;
    auto sa=SA::construct_sa(S);
    auto lcp=SA::construct_lcp(S,sa);
    auto rid=sa;
    REP(i,sa.size())rid[sa[i]]=i;
    vector<int> ids;
    for(auto &it:sa){
        if(N-it>=max_len)ids.pb(it);
    }
    seg_tree st(N+1,lcp);
    auto cmp=[&](int l,int r){
        if(rid[l]>rid[r])swap(l,r);
        if(l==r)return true;
        return st.get(rid[l]+1,rid[r]+1)>=max_len;
    };
    auto f=[&](int id){
        int now_cost=0;
        int lb=1;
        int ub=1;
        REP(i,N){
            if(i+max_len>N||rid[i]<=rid[id]||cmp(i,id))
                chmax(ub,i+max_len+1);
            else chmax(ub,i+max_len);
            if(i+1>=ub)return false;
            if(i+1==lb){
                lb=ub;
                now_cost++;
            }
        }
        return now_cost<=K;
    };
    int ok=ids.size()-1,ng=-1;
    while(ok-ng>1){
        const int mid=(ok+ng)/2;
        if(f(ids[mid]))ok=mid;
        else ng=mid;
    }
    REP(i,max_len)cout<<S[ids[ok]+i];cout<<endl;
    return 0;
}

Submission

Task問題 B - 数字列をカンマで分ける問題 / Problem where Commas Separate Digits
User nameユーザ名 btk
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 200
Source lengthソースコード長 4499 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask_02_ex1.txt,subtask_03_ex2.txt,subtask_03_ex3.txt
Dataset1 100 / 100 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 100 / 100 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 0 / 200 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 0 / 200 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 0 / 400 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask_01_01.txt AC 2 ms 2304 KB
subtask_01_02.txt AC 2 ms 2304 KB
subtask_01_03.txt AC 2 ms 2304 KB
subtask_01_04.txt AC 2 ms 2304 KB
subtask_01_05.txt AC 2 ms 2304 KB
subtask_01_06.txt AC 2 ms 2304 KB
subtask_01_07.txt AC 2 ms 2304 KB
subtask_01_08.txt AC 2 ms 2304 KB
subtask_01_09.txt AC 2 ms 2304 KB
subtask_01_10.txt AC 2 ms 2304 KB
subtask_01_11.txt AC 2 ms 2304 KB
subtask_01_12.txt AC 2 ms 2304 KB
subtask_01_13.txt AC 2 ms 2304 KB
subtask_01_14.txt AC 2 ms 2304 KB
subtask_01_15.txt AC 2 ms 2304 KB
subtask_01_16.txt AC 2 ms 2304 KB
subtask_01_17.txt AC 2 ms 2304 KB
subtask_02_01.txt AC 2 ms 2304 KB
subtask_02_02.txt AC 2 ms 2304 KB
subtask_02_03.txt AC 2 ms 2304 KB
subtask_02_04.txt AC 2 ms 2304 KB
subtask_02_05.txt AC 2 ms 2304 KB
subtask_02_06.txt AC 2 ms 2304 KB
subtask_02_07.txt AC 2 ms 2304 KB
subtask_02_08.txt AC 2 ms 2304 KB
subtask_02_09.txt AC 2 ms 2304 KB
subtask_02_10.txt AC 2 ms 2304 KB
subtask_02_11.txt AC 2 ms 2304 KB
subtask_02_12.txt AC 2 ms 2304 KB
subtask_02_13.txt AC 2 ms 2304 KB
subtask_02_14.txt AC 2 ms 2304 KB
subtask_02_ex1.txt AC 2 ms 2304 KB
subtask_03_01.txt AC 2 ms 2304 KB
subtask_03_02.txt WA
subtask_03_03.txt AC 2 ms 2304 KB
subtask_03_04.txt AC 2 ms 2304 KB
subtask_03_05.txt AC 2 ms 2304 KB
subtask_03_06.txt AC 2 ms 2304 KB
subtask_03_07.txt AC 2 ms 2304 KB
subtask_03_08.txt AC 2 ms 2304 KB
subtask_03_09.txt AC 2 ms 2304 KB
subtask_03_10.txt WA
subtask_03_11.txt AC 2 ms 2304 KB
subtask_03_12.txt WA
subtask_03_13.txt AC 2 ms 2304 KB
subtask_03_14.txt AC 2 ms 2304 KB
subtask_03_15.txt AC 2 ms 2304 KB
subtask_03_ex2.txt AC 2 ms 2304 KB
subtask_03_ex3.txt AC 2 ms 2304 KB
subtask_04_01.txt WA
subtask_04_02.txt AC 6 ms 2432 KB
subtask_04_03.txt AC 3 ms 2432 KB
subtask_04_04.txt AC 3 ms 2432 KB
subtask_04_05.txt WA
subtask_04_06.txt AC 3 ms 2432 KB
subtask_04_07.txt AC 3 ms 2432 KB
subtask_04_08.txt AC 4 ms 2432 KB
subtask_04_09.txt AC 3 ms 2432 KB
subtask_04_10.txt WA
subtask_04_11.txt AC 3 ms 2432 KB
subtask_04_12.txt WA
subtask_04_13.txt AC 3 ms 2304 KB
subtask_04_14.txt WA
subtask_04_15.txt AC 3 ms 2432 KB
subtask_05_01.txt WA
subtask_05_02.txt WA
subtask_05_03.txt AC 121 ms 5576 KB
subtask_05_04.txt AC 150 ms 5576 KB
subtask_05_05.txt WA
subtask_05_06.txt WA
subtask_05_07.txt WA
subtask_05_08.txt AC 259 ms 5452 KB
subtask_05_09.txt AC 122 ms 5200 KB
subtask_05_10.txt WA
subtask_05_11.txt AC 201 ms 5576 KB
subtask_05_12.txt WA
subtask_05_13.txt AC 356 ms 4984 KB
subtask_05_14.txt AC 150 ms 5368 KB
subtask_05_15.txt AC 97 ms 3872 KB