Submission #497212

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
497212	2021-12-22T17:47:09 Z	julian33	Rima (COCI17_rima)	C++14	56 / 140	1000 ms	52460 KB

rima

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cerr<<vars<<" = ";
    string delim="";
    (...,(cerr<<delim<<values,delim=", "));
    cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif

#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);} 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxN=3e6+5; //make sure this is right
const int mod=1e9+7;
const int mod2=988244353;
const int b=131;

/*
lets denote a string by its identity
{hash of 1->n-1, full hash, len(s)} -> {x,y,l}
all strings with same x can be considered as part of same component
dp[y] = dp[x] + sz(x)
*/

struct H {
    typedef uint64_t ull;
    ull x; H(ull x=0) : x(x) {}
#define OP(O,A,B) H operator O(H o) { ull r = x; asm \
    (A "addq %%rdx, %0\n adcq $0,%0" : "+a"(r) : B); return r; }
    OP(+,,"d"(o.x)) OP(*,"mul %1\n", "r"(o.x) : "rdx")
    H operator-(H o) { return *this + ~o.x; }
    ull get() const { return x + !~x; }
    bool operator==(H o) const { return get() == o.get(); }
    bool operator<(H o) const { return get() < o.get(); }
};
static const H C = (ll)1e11+3; // (order ~ 3e9; random also ok)

struct HashInterval {
    vector<H> ha, pw;
    HashInterval(string& str) : ha(sz(str)+1), pw(ha) {
        pw[0] = 1;
        for(int i=1;i<=sz(str);i++)
            ha[i] = ha[i-1] * C + str[i-1],
            pw[i] = pw[i-1] * C;
    }
    H hashInterval(int a, int b) { // hash [a, b)
        return ha[b] - ha[a] * pw[b - a];
    }
};

struct identity{
    H x,y;
    int l;
    bool operator<(const identity &o) const{
        return l<o.l;
    }
};

map<H,int> dp,cnt;

int main(){
    cin.sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #ifdef LOCAL
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif

    int n; cin>>n;
    vector<identity> all;
    for(int i=0;i<n;i++){
        string s; cin>>s;
        reverse(s.begin(),s.end());
        identity cur;
        HashInterval h(s);
        cur.x=h.hashInterval(0,sz(s)-1);
        cur.y=h.hashInterval(0,sz(s));
        cnt[cur.x]++;
        cur.l=sz(s);
        all.pb(cur);
    }
    sort(all.begin(),all.end());
    int ans=0;
    for(auto &[x,y,l]:all){
        if(!dp.count(x)) dp[y]=cnt[x];
        else dp[y]=dp[x]+cnt[x];
        maxa(ans,dp[y]);
    }
    cout<<ans<<"\n";
}

Compilation message

rima.cpp: In function 'int main()':
rima.cpp:101:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |     for(auto &[x,y,l]:all){
      |               ^

Subtask #1

56.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Execution timed out	1100 ms	52460 KB	Time limit exceeded
5	Correct	27 ms	720 KB	Output is correct
6	Incorrect	9 ms	5476 KB	Output isn't correct
7	Incorrect	8 ms	5488 KB	Output isn't correct
8	Incorrect	8 ms	5420 KB	Output isn't correct
9	Incorrect	40 ms	5880 KB	Output isn't correct
10	Incorrect	10 ms	5460 KB	Output isn't correct