Submission #817261


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) && prefix(j,v[idx+1]) && 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 4155 Byte
Status
Exec Time 4434 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 4295 ms 6272 KB
abten0 97 ms 3860 KB
allsame0 4317 ms 20436 KB
allsame_ex0 4434 ms 23352 KB
bigrand0 41 ms 2560 KB
bigrand1 51 ms 3328 KB
firstlast0 62 ms 3584 KB
firstlast1 66 ms 3712 KB
fullrand0 62 ms 3712 KB
fullrand1 62 ms 3712 KB
fullrand2 58 ms 3584 KB
kaidan0 3180 ms 10752 KB
maxrand0 48 ms 3444 KB
maxrand1 44 ms 3328 KB
maxrand2 45 ms 3456 KB
roll_hyper0 79 ms 4096 KB
roll_hyper1 79 ms 4096 KB
roll_hyper_r0 80 ms 4096 KB
rolling0 72 ms 3968 KB
rolling1 73 ms 3968 KB
smallc0 727 ms 3584 KB
smallc1 824 ms 3584 KB
smallrand0 4 ms 256 KB
smallrand1 4 ms 256 KB
smallrand2 4 ms 256 KB
zzza0 21 ms 2816 KB