Submission #816869


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));
        if ( SZ(v)>500 ) v.resize(500);
        nv.clear();
        string *last=NULL;
        for ( auto &j:v ) {
            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());
    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 3823 Byte
Status
Exec Time 2050 ms
Memory 14740 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 1362 ms 3584 KB
abten0 120 ms 3980 KB
allsame0 2003 ms 12180 KB
allsame_ex0 2050 ms 14740 KB
bigrand0 40 ms 2560 KB
bigrand1 49 ms 3292 KB
firstlast0 59 ms 3584 KB
firstlast1 64 ms 3692 KB
fullrand0 60 ms 3712 KB
fullrand1 65 ms 3712 KB
fullrand2 61 ms 3584 KB
kaidan0 1480 ms 7332 KB
maxrand0 49 ms 3456 KB
maxrand1 43 ms 3328 KB
maxrand2 45 ms 3328 KB
roll_hyper0 80 ms 4096 KB
roll_hyper1 78 ms 4096 KB
roll_hyper_r0 81 ms 4096 KB
rolling0 71 ms 3968 KB
rolling1 70 ms 3968 KB
smallc0 680 ms 3584 KB
smallc1 771 ms 3584 KB
smallrand0 4 ms 256 KB
smallrand1 4 ms 256 KB
smallrand2 4 ms 256 KB
zzza0 21 ms 2816 KB