oj.uz

Submission #715646

# Submission time Handle Problem Language Result Execution time Memory
715646 2023-03-27T11:36:30 Z arashMLG Anagramistica (COCI21_anagramistica) C++17
110 / 110
 60 ms 40336 KB 
#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...) 42
#endif
using namespace std;

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

typedef long long     ll;
typedef long double   ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll>   pll;


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 2e3 + 23;
const ll mod = 1e9 + 7;
const ll mod1 = 1006969;
const ll B = 32323;
const ll B2 = rng() % 100+ 27;
const int LOG = 23;
const ll inf = 1e18;


#define F           first
#define S           second
#define pb          push_back
#define ms(x,y)     memset((x) , (y) , sizeof (x))
#define done        return cout<<endl , 0;
#define kill(x)     cout<<x<<endl, exit(0);
#define isIn(x,s,e) ((x) >= (s) && (x) <= e)
#define all(x)      x.begin(),x.end()
#define sz(x)       (int)x.size()
#define pc(x)       __builtin_popcount(x)
#define ctz(x)      __builtin_ctz(x)
#define MinHeap(x)  priority_queue<x, vector<x> , greater<x> >
#define MaxHeap(x)  priority_queue<x, vector<x>>
#define int      ll

ll pw(ll a, ll b, ll md = mod){ll res = 1; while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int get_hash(string s,int modd,int base) {
    int hsh =0;
    for(int i = 0; i < sz(s);i ++) {
        hsh = (hsh * base + s[i] - 'a' +1) % modd;
    }
    return hsh;
}

pll get_hash(string s) {
    return {get_hash(s,mod1,B), get_hash(s,mod,B2)};
}

int n,k;
vector<pll> v;
int dp[N][N];
int c[N][N];

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    for(int i = 0 ;i < N; i++) {
        c[i][0] = 1;
        c[i][i] = 1;
        for(int j = 1; j < i ; j++) {
            c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
        }
    }
    cin>>n>>k;
    for(int i =0; i< n; i++) {
        string s; cin>>s; sort(all(s));
        v.pb(get_hash(s));
    }
    v.pb({-1,-1});
    sort(all(v));
    debug(v);
    int cnt = 0;
    dp[0][0] = 1;
    for(int i = 1; i<= n;i ++) {
        if(v[i] != v[i-1]) {
            cnt = 0;
        }
        for(int l = 0 ; l <= k ;l ++) {
            dp[i][l] = dp[i-1][l];
        }
        for(int j = 0 ;j <= cnt; j ++) {
            for(int l = (j+1)*j/2 ; l <= k ;l ++) {
                (dp[i][l] += c[cnt][j] * dp[i-cnt-1][l - (j+1) * j /2]) %= mod;
            }
        }
        cnt++;
    }
    cout<<dp[n][k];
    done;
}

Compilation message

anagramistica.cpp: In function 'int32_t main()':
anagramistica.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 42
      |                    ^~
anagramistica.cpp:79:5: note: in expansion of macro 'debug'
   79 |     debug(v);
      |     ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23508 KB Output is correct
2 Correct 15 ms 23508 KB Output is correct
3 Correct 13 ms 23508 KB Output is correct
4 Correct 13 ms 23536 KB Output is correct
5 Correct 13 ms 23508 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28500 KB Output is correct
2 Correct 15 ms 29488 KB Output is correct
3 Correct 19 ms 30524 KB Output is correct
4 Correct 17 ms 31556 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23508 KB Output is correct
2 Correct 15 ms 23508 KB Output is correct
3 Correct 13 ms 23508 KB Output is correct
4 Correct 13 ms 23536 KB Output is correct
5 Correct 13 ms 23508 KB Output is correct
6 Correct 16 ms 28500 KB Output is correct
7 Correct 15 ms 29488 KB Output is correct
8 Correct 19 ms 30524 KB Output is correct
9 Correct 17 ms 31556 KB Output is correct
10 Correct 15 ms 26752 KB Output is correct
11 Correct 16 ms 26580 KB Output is correct
12 Correct 15 ms 27604 KB Output is correct
13 Correct 17 ms 28500 KB Output is correct
14 Correct 17 ms 30420 KB Output is correct
15 Correct 18 ms 30484 KB Output is correct
16 Correct 19 ms 33936 KB Output is correct
17 Correct 60 ms 40336 KB Output is correct
18 Correct 16 ms 31608 KB Output is correct