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
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 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