Submission #817210


Source Code Expand

Copy
// {{{ by shik
#include <bits/stdc++.h>
#include <unistd.h>
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x),end(x)
#define REP(i,n) for ( int i=0; i<int(n); i++ )
#define REP1(i,a,b) for ( int i=(a); i<=int(b); i++ )
#define FOR(it,c) for ( auto it=(c).begin(); it!=(c).end(); it++ )
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;

#ifdef SHIK
template<typename T>
void _dump( const char* s, T&& head ) { cerr<<s<<"="<<head<<endl; }

template<typename T, typename... Args>
void _dump( const char* s, T&& head, Args&&... tail ) {
    int c=0;
    while ( *s!=',' || c!=0 ) {
        if ( *s=='(' || *s=='[' || *s=='{' ) c++;
        if ( *s==')' || *s==']' || *s=='}' ) c--;
        cerr<<*s++;
    }
    cerr<<"="<<head<<", ";
    _dump(s+1,tail...);
}

#define dump(...) do { \
    fprintf(stderr, "%s:%d - ", __PRETTY_FUNCTION__, __LINE__); \
    _dump(#__VA_ARGS__, __VA_ARGS__); \
} while (0)

template<typename Iter>
ostream& _out( ostream &s, Iter b, Iter e ) {
    s<<"[";
    for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
    s<<"]";
    return s;
}

template<typename A, typename B>
ostream& operator <<( ostream &s, const pair<A,B> &p ) { return s<<"("<<p.first<<","<<p.second<<")"; }
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) { return _out(s,ALL(c)); }
template<typename T, size_t N>
ostream& operator <<( ostream &s, const array<T,N> &c ) { return _out(s,ALL(c)); }
template<typename T>
ostream& operator <<( ostream &s, const set<T> &c ) { return _out(s,ALL(c)); }
template<typename A, typename B>
ostream& operator <<( ostream &s, const map<A,B> &c ) { return _out(s,ALL(c)); }
#else
#define dump(...)
#endif

template<typename T>
void _R( T &x ) { cin>>x; }
void _R( int &x ) { scanf("%d",&x); }
void _R( long long &x ) { scanf("%" PRId64,&x); }
void _R( double &x ) { scanf("%lf",&x); }
void _R( char &x ) { scanf(" %c",&x); }
void _R( char *x ) { scanf("%s",x); }

void R() {}
template<typename T, typename... U>
void R( T& head, U&... tail ) {
    _R(head);
    R(tail...);
}

template<typename T>
void _W( const T &x ) { cout<<x; }
void _W( const int &x ) { printf("%d",x); }
template<typename T>
void _W( const vector<T> &x ) {
    for ( auto i=x.cbegin(); i!=x.cend(); i++ ) {
        if ( i!=x.cbegin() ) putchar(' ');
        _W(*i);
    }
}

void W() {}
template<typename T, typename... U>
void W( const T& head, const U&... tail ) {
    _W(head);
    putchar(sizeof...(tail)?' ':'\n');
    W(tail...);
}

#ifdef SHIK
#define FILEIO(...)
#else
#define FILEIO(name) do {\
    freopen(name ".in","r",stdin); \
    freopen(name ".out","w",stdout); \
} while (0)
#endif

// }}}

const int N=2016;
const int M=1e4+10;

bool prefix( const string &a, const string &b ) {
    if ( SZ(a)>=SZ(b) ) return 0;
    return strncmp(a.data(),b.data(),SZ(a))==0;
}

int n,m,l[N],mi[N];
string s[N];
bitset<M> can[N];
int main() {
    R(n,m);
    REP1(i,1,n) R(s[i]);
    REP1(i,1,n) l[i]=SZ(s[i]);
    mi[n]=n;
    for ( int i=n-1; i>=1; i-- ) {
        if ( s[i]<s[mi[i+1]] ) mi[i]=i;
        else mi[i]=mi[i+1];
    }
    can[n+1][0]=1;
    for ( int i=n; i>=1; i-- ) can[i]=can[i+1]|(can[i+1]<<l[i]);
    vector<string> v,nv;
    v.PB("");
    REP1(i,1,n) {
        sort(ALL(v));
        v.erase(unique(ALL(v)),v.end());
        dump(i,SZ(v));
        nv.clear();
        string *last=NULL;
        int idx=0,cnt=0;
        for ( auto &j:v ) {
            idx++;
            if ( last && !prefix(*last,j) ) continue;
            // if ( idx+1<SZ(v) && SZ(v[idx+1])>SZ(j) && strncmp(s[mi[i]].data(),v[idx+1].data()+SZ(j),SZ(v[idx+1])-SZ(j))>0 ) continue;
            if ( ++cnt>800 ) continue;
            last=&j;
            if ( can[i+1][m-SZ(j)] ) nv.PB(j);
            int nl=SZ(j)+l[i];
            if ( nl<=m && can[i+1][m-nl] ) nv.PB(j+s[i]);
        }
        v.swap(nv);
    }
    assert(!v.empty());
    sort(ALL(v));
    W(v[0]);
    return 0;
}

Submission Info

Submission Time
Task F - 文字列大好きいろはちゃん / Iroha Loves Strings
User shik
Language C++14 (GCC 5.4.1)
Score 0
Code Size 4158 Byte
Status
Exec Time 4175 ms
Memory 23352 KB

Compile Error

./Main.cpp: In function ‘void _R(long long int&)’:
./Main.cpp:62:46: warning: format ‘%ld’ expects argument of type ‘long int*’, but argument 2 has type ‘long long int*’ [-Wformat=]
 void _R( long long &x ) { scanf("%" PRId64,&x); }
                                              ^
./Main.cpp: In function ‘void _R(int&)’:
./Main.cpp:61:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 void _R( int &x ) { scanf("%d",&x); }
                                   ^
./Main.cpp: In function ‘void _R(long long int&)’:
./Main.cpp:62:47: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 void _R( long long &x ) { scanf("%" PRId64,&x); }
                                               ^
./Main.cpp: In function ‘void _R(double&)’:
./Main.cpp:63:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-resu...

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 0_sample01, 0_sample02, 0_sample03
All 0 / 1500 0_sample01, 0_sample02, 0_sample03, abab0, abten0, allsame0, allsame_ex0, bigrand0, bigrand1, firstlast0, firstlast1, fullrand0, fullrand1, fullrand2, kaidan0, maxrand0, maxrand1, maxrand2, roll_hyper0, roll_hyper1, roll_hyper_r0, rolling0, rolling1, smallc0, smallc1, smallrand0, smallrand1, smallrand2, zzza0
Case Name Status Exec Time Memory
0_sample01 4 ms 256 KB
0_sample02 4 ms 256 KB
0_sample03 4 ms 256 KB
abab0 2844 ms 5120 KB
abten0 119 ms 3980 KB
allsame0 4016 ms 20436 KB
allsame_ex0 4175 ms 23352 KB
bigrand0 40 ms 2560 KB
bigrand1 50 ms 3292 KB
firstlast0 59 ms 3584 KB
firstlast1 62 ms 3712 KB
fullrand0 60 ms 3712 KB
fullrand1 63 ms 3712 KB
fullrand2 60 ms 3680 KB
kaidan0 2949 ms 10752 KB
maxrand0 50 ms 3456 KB
maxrand1 43 ms 3328 KB
maxrand2 45 ms 3456 KB
roll_hyper0 81 ms 4096 KB
roll_hyper1 79 ms 4096 KB
roll_hyper_r0 89 ms 4096 KB
rolling0 73 ms 3968 KB
rolling1 74 ms 3968 KB
smallc0 676 ms 3584 KB
smallc1 767 ms 3584 KB
smallrand0 4 ms 256 KB
smallrand1 4 ms 256 KB
smallrand2 4 ms 256 KB
zzza0 20 ms 2816 KB