Submission #1001274
Source Code Expand
#include <bits/stdc++.h> #define FOR(i,a,b) for( ll i = (a); i < (ll)(b); i++ ) #define REP(i,n) FOR(i,0,n) #define YYS(x,arr) for(auto& x:arr) #define ALL(x) (x).begin(),(x).end() #define SORT(x) sort( (x).begin(),(x).end() ) #define REVERSE(x) reverse( (x).begin(),(x).end() ) #define UNIQUE(x) (x).erase( unique( ALL( (x) ) ) , (x).end() ) #define PW(x) (1LL<<(x)) #define SZ(x) ((ll)(x).size()) #define SHOW(x) cout << #x << " = " << x << endl #define pb emplace_back #define fi first #define se second using namespace std; typedef long double ld; typedef long long int ll; typedef pair<int,int> pi; typedef pair<ll,ll> pl; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<bool> vb; typedef vector<ld> vd; typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<vpl> gr; typedef vector<vl> ml; typedef vector<vd> md; typedef vector<vi> mi; const ll INF = (ll)1e9 + 10; const ll INFLL = (ll)1e18 + 10; const ld EPS = 1e-12; const ll MOD = 1e9+7; template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); } template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); } template<class T> inline T sq( T a ){ return a * a; } ll in(){ ll x; scanf( "%lld" , &x ); return x; } char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; } // head template<class T> class MinOp{ public: T operator () ( T a , T b ){ return min( a , b ); } }; template<class T> class MaxOp{ public: T operator () ( T a , T b ){ return max( a , b ); } }; template<typename T, class OpFunc> struct Segtree{ T ID; vector<T> node; int size; OpFunc op; void init( int n , OpFunc opfunc , T identity ){ op = opfunc; ID = identity; size = 1; while( size < n ) size *= 2; node = vector<T>( size*2-1 , ID ); } void update( int k , T x ){ k += size-1; node[k] = x; while( k > 0 ){ k = (k-1)/2; node[k] = op( node[k*2+1] , node[k*2+2] ); } } T query( int a , int b , int k , int l , int r ){ if( a <= l && r <= b ){ return node[k]; } else if( b <= l || r <= a ){ return ID; } else { T chl = query( a , b , k*2+1 , l , (l+r)/2 ); T chr = query( a , b , k*2+2 , (l+r)/2 , r ); return op( chl , chr ); } } T query( int a , int b ){ return query( a , b , 0 , 0 , size ); } T get( int a ){ return node[a+size-1]; } }; struct SA : public vi{ int n, k; vi rank, tmp; bool compare( int i , int j ){ if( rank[i] != rank[j] ) return rank[i] < rank[j]; int ri = i + k <= n ? rank[i+k] : -1; int rj = j + k <= n ? rank[j+k] : -1; return ri < rj; } struct Compare_SA{ SA *sa; Compare_SA( SA *s ) : sa(s) {} bool operator() ( const int &i , const int &j ){ return sa->compare( i , j ); } }; void init( string S ){ n = S.length(); resize( n+1 ); rank = tmp = vi( n+1 ); REP( i , n+1 ){ at(i) = i; rank[i] = i < n ? S[i] : -1; } for( k = 1; k <= n; k *= 2 ){ sort( begin() , end() , Compare_SA(this) ); tmp[at(0)] = 0; FOR( i , 1 , n+1 ) tmp[at(i)] = tmp[at(i-1)] + (compare(at(i-1),at(i))?1:0); REP( i , n+1 ) rank[i] = tmp[i]; } } }; struct LCP : public vi{ void init( string S , const SA &sa ){ int n = S.length(); vi rank(n+1); REP( i , n+1 ) rank[sa[i]] = i; int h = 0; resize( n , 0 ); REP( i , n ){ int j = sa[rank[i]-1]; if( h > 0 ) h--; for( ; j+h < n && i+h < n; h++ ) if( S[j+h] != S[i+h] ) break; at(rank[i]-1) = h; } } }; struct RangeLCP{ SA sa; LCP lcp; Segtree<int,MinOp<int> > seg; void init( string s ){ sa.init( s ); lcp.init( s , sa ); seg.init( SZ(s) , MinOp<int>() , INF ); REP( i , SZ(s) ){ seg.update( i , lcp[i] ); } } int sa_query( int l , int r ){ return seg.query( l , r ); } int pos_query( int l , int r ){ int a = sa.rank[l]; int b = sa.rank[r]; if( a > b ){ swap( a , b ); } return seg.query( a , b ); } }; int n, k, l; string s; SA sa; vi v; RangeLCP lcp; bool check( int x ){ int cur = 0; int cnt = 0; while( cur < n ){ // cout << cur << " " << cnt << endl; if( cnt > k ){ return false; } if( sa.rank[cur] > sa.rank[x] and lcp.pos_query( x , cur ) < l ){ cur += l-1; } else { cur += l; } cnt++; } return true; } int main(){ k = in(); s = stin(); n = SZ(s); sa.init( s ); lcp.init( s ); l = ( n + k ) / ( k + 1 ); /* cout << check( 5 ) << endl; return 0; */ REP( i , n+1 ){ if( sa[i] <= n - l ){ v.pb( sa[i] ); } } int lb = -1, ub = SZ(v); while( ub - lb > 1 ){ int md = ( lb + ub ) / 2; if( check( v[md] ) ){ ub = md; } else { lb = md; } } /* SHOW( v[ub] ); SHOW( check( v[ub] ) ); */ FOR( i , v[ub] , v[ub]+l ){ printf( "%c" , s[i] ); } printf( "\n" ); return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Problem where Commas Separate Digits |
User | joisino |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 5295 Byte |
Status | AC |
Exec Time | 477 ms |
Memory | 5112 KB |
Compile Error
./Main.cpp: In function ‘ll in()’: ./Main.cpp:44:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] ll in(){ ll x; scanf( "%lld" , &x ); return x; } ^ ./Main.cpp: In function ‘std::string stin()’: ./Main.cpp:45:66: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; } ^
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 |
|
|
|
|
|
|
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 | 3 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 | 3 ms | 256 KB |
subtask_03_ex2.txt | AC | 3 ms | 256 KB |
subtask_03_ex3.txt | AC | 3 ms | 256 KB |
subtask_04_01.txt | AC | 6 ms | 384 KB |
subtask_04_02.txt | AC | 5 ms | 384 KB |
subtask_04_03.txt | AC | 5 ms | 384 KB |
subtask_04_04.txt | AC | 4 ms | 384 KB |
subtask_04_05.txt | AC | 4 ms | 384 KB |
subtask_04_06.txt | AC | 4 ms | 384 KB |
subtask_04_07.txt | AC | 4 ms | 384 KB |
subtask_04_08.txt | AC | 4 ms | 384 KB |
subtask_04_09.txt | AC | 4 ms | 256 KB |
subtask_04_10.txt | AC | 4 ms | 384 KB |
subtask_04_11.txt | AC | 4 ms | 384 KB |
subtask_04_12.txt | AC | 4 ms | 384 KB |
subtask_04_13.txt | AC | 3 ms | 256 KB |
subtask_04_14.txt | AC | 3 ms | 256 KB |
subtask_04_15.txt | AC | 4 ms | 256 KB |
subtask_05_01.txt | AC | 477 ms | 5112 KB |
subtask_05_02.txt | AC | 379 ms | 5112 KB |
subtask_05_03.txt | AC | 294 ms | 5112 KB |
subtask_05_04.txt | AC | 187 ms | 5112 KB |
subtask_05_05.txt | AC | 183 ms | 5112 KB |
subtask_05_06.txt | AC | 181 ms | 5112 KB |
subtask_05_07.txt | AC | 179 ms | 5112 KB |
subtask_05_08.txt | AC | 175 ms | 4728 KB |
subtask_05_09.txt | AC | 175 ms | 4344 KB |
subtask_05_10.txt | AC | 186 ms | 5112 KB |
subtask_05_11.txt | AC | 183 ms | 5112 KB |
subtask_05_12.txt | AC | 168 ms | 5112 KB |
subtask_05_13.txt | AC | 145 ms | 4312 KB |
subtask_05_14.txt | AC | 162 ms | 4884 KB |
subtask_05_15.txt | AC | 68 ms | 2396 KB |