Submission #817298


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 && rand()%2==0 ) 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 4170 Byte
Status
Exec Time 5260 ms
Memory 37272 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 4726 ms 7188 KB
abten0 98 ms 3860 KB
allsame0
allsame_ex0
bigrand0 42 ms 2560 KB
bigrand1 52 ms 3292 KB
firstlast0 62 ms 3584 KB
firstlast1 65 ms 3712 KB
fullrand0 63 ms 3712 KB
fullrand1 63 ms 3712 KB
fullrand2 59 ms 3692 KB
kaidan0
maxrand0 46 ms 3456 KB
maxrand1 44 ms 3328 KB
maxrand2 46 ms 3456 KB
roll_hyper0 79 ms 4096 KB
roll_hyper1 79 ms 4096 KB
roll_hyper_r0 82 ms 4096 KB
rolling0 71 ms 3968 KB
rolling1 71 ms 3968 KB
smallc0 726 ms 3584 KB
smallc1 828 ms 3584 KB
smallrand0 4 ms 256 KB
smallrand1 4 ms 256 KB
smallrand2 4 ms 256 KB
zzza0 22 ms 2816 KB