Submission #817017


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];
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]);
    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;
        for ( auto &j:v ) {
            idx++;
            if ( idx>500 ) continue;
            if ( last && !prefix(*last,j) ) 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 3879 Byte
Status
Exec Time 2029 ms
Memory 14684 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 1377 ms 3968 KB
abten0 122 ms 3980 KB
allsame0 1912 ms 12312 KB
allsame_ex0 2029 ms 14684 KB
bigrand0 41 ms 2560 KB
bigrand1 51 ms 3292 KB
firstlast0 60 ms 3584 KB
firstlast1 63 ms 3692 KB
fullrand0 62 ms 3712 KB
fullrand1 65 ms 3712 KB
fullrand2 61 ms 3680 KB
kaidan0 1446 ms 7424 KB
maxrand0 50 ms 3456 KB
maxrand1 44 ms 3328 KB
maxrand2 50 ms 3328 KB
roll_hyper0 83 ms 4096 KB
roll_hyper1 78 ms 4096 KB
roll_hyper_r0 84 ms 4096 KB
rolling0 72 ms 3968 KB
rolling1 72 ms 3968 KB
smallc0 675 ms 3584 KB
smallc1 767 ms 3584 KB
smallrand0 4 ms 256 KB
smallrand1 4 ms 256 KB
smallrand2 4 ms 256 KB
zzza0 21 ms 2816 KB