Submission #1127770
Source Code Expand
#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 Info
Submission Time | |
---|---|
Task | B - Problem where Commas Separate Digits |
User | btk15049 |
Language | C++14 (GCC 5.4.1) |
Score | 200 |
Code Size | 4499 Byte |
Status | WA |
Exec Time | 547 ms |
Memory | 5576 KB |
Judge Result
Set Name | Sample | Dataset1 | Dataset2 | Dataset3 | Dataset4 | Dataset5 | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | 100 / 100 | 0 / 200 | 0 / 200 | 0 / 400 | ||||||||||||||||||
Status |
|
|
|
|
|
|
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 | 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 | 2 ms | 2304 KB |
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 | 2 ms | 2304 KB |
subtask_03_11.txt | AC | 2 ms | 2304 KB |
subtask_03_12.txt | WA | 1 ms | 2304 KB |
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 | 5 ms | 2432 KB |
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 | 3 ms | 2432 KB |
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 | 3 ms | 2432 KB |
subtask_04_11.txt | AC | 3 ms | 2432 KB |
subtask_04_12.txt | WA | 3 ms | 2432 KB |
subtask_04_13.txt | AC | 3 ms | 2304 KB |
subtask_04_14.txt | WA | 2 ms | 2304 KB |
subtask_04_15.txt | AC | 3 ms | 2432 KB |
subtask_05_01.txt | WA | 547 ms | 5576 KB |
subtask_05_02.txt | WA | 491 ms | 5576 KB |
subtask_05_03.txt | AC | 121 ms | 5576 KB |
subtask_05_04.txt | AC | 150 ms | 5576 KB |
subtask_05_05.txt | WA | 150 ms | 5576 KB |
subtask_05_06.txt | WA | 150 ms | 5576 KB |
subtask_05_07.txt | WA | 151 ms | 5576 KB |
subtask_05_08.txt | AC | 259 ms | 5452 KB |
subtask_05_09.txt | AC | 122 ms | 5200 KB |
subtask_05_10.txt | WA | 166 ms | 5576 KB |
subtask_05_11.txt | AC | 201 ms | 5576 KB |
subtask_05_12.txt | WA | 186 ms | 5576 KB |
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 |