oj.uz

Submission #770431

# Submission time Handle Problem Language Result Execution time Memory
770431 2023-07-01T07:56:53 Z JakobZorz Cubeword (CEOI19_cubeword) C++14
100 / 100
 164 ms 15124 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <stack>
#include <limits.h>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <map>
#include <cstring>
#include <sstream>
 
#pragma GCC target("popcnt")
 
typedef long long ll;
typedef long double ld;
using namespace std;
const int MOD = 1e9+7;
typedef pair<ld,ld> point;
#define x first
#define y second

//#define SEGTREE
//#define TREE
//#define DSU
#define MATH
 
#ifdef SEGTREE
template<class Type>
class SegmentTree {
    Type (*func)(Type a, Type b);
    vector<Type> nodes;
    vector<int> l;
    vector<int> r;
    int size_log2;
    Type neutral;
    
    void init_node(int node) {
        if(node >= (1 << size_log2))
            return;
        
        l[2 * node] = l[node];
        r[2 * node] = (l[node] + r[node]) / 2;
        init_node(2 * node);
        
        l[2 * node + 1] = (l[node] + r[node]) / 2;
        r[2 * node + 1] = r[node];
        init_node(2 * node + 1);
        
        nodes[node] = func(nodes[2 * node], nodes[2 * node + 1]);
    }
    
    void update_node(int node) {
        if(node < (1 << size_log2))
            nodes[node] = func(nodes[2 * node], nodes[2 * node + 1]);
        
        if(node != 1)
            update_node(node / 2);
    }
    
    Type get(int node, int ll_, int rr) {
        if(rr <= l[node] || ll_ >= r[node])
            return neutral;
        
        if(ll_ <= l[node] && rr >= r[node])
            return nodes[node];
        
        Type left = get(2 * node, ll_, rr);
        Type right = get(2 * node + 1, ll_, rr);
        
        return func(left, right);
    }
    
public:
    SegmentTree(Type (*func)(Type a, Type b), vector<Type> vector, Type neutral) : func(func), neutral(neutral) {
        size_log2 = 0;
        while((1 << size_log2) < vector.size())
            size_log2++;
        
        nodes.resize((1 << size_log2) * 2);
        l.resize((1 << size_log2) * 2);
        r.resize((1 << size_log2) * 2);
        
        for(int i = 0; i < vector.size(); i++)
            nodes[(1 << size_log2) + i] = vector[i];
        
        l[1] = 0;
        r[1] = 1 << size_log2;
        init_node(1);
    }
    
    void set(int idx, Type el) {
        nodes[(1 << size_log2) + idx] = el;
        update_node((1 << size_log2) + idx);
    }
    
    Type get(int l, int r) {
        return get(1, l, r);
    }
    
    Type get(int idx) {
        return nodes[(1 << size_log2) + idx];
    }
    
    Type get() {
        return nodes[1];
    }
    
    int get_first_larger_or_eq_than(int bound) {
        return get_first_larger_or_eq_than(1, bound);
    }
    
    int get_first_larger_or_eq_than(int node, int bound) {
        if(node >= (1 << size_log2)) {
            return node - (1 << size_log2);
        }
        
        if(nodes[node * 2] > bound)
            return get_first_larger_or_eq_than(node * 2, bound);
        else
            return get_first_larger_or_eq_than(node * 2 + 1, bound - nodes[node * 2]);
    }
};
 
#endif
 
#ifdef TREE
#define POW 18
 
struct Node {
    int parents[POW];
    vector<int> conns;
    int depth;
    int value;
    int subtree_depth;
    int subtree_size;
    int euler;
    int val;
    int res;
};
 
ll add(ll a, ll b) {
    return a + b;
}
 
Node nodes[200000];
int n;
 
int setup(int node, int depth, int euler, ll dist) {
    dist += nodes[node].value;
    nodes[node].depth = depth;
    nodes[node].euler = euler++;
    
    
    for(int i = 1; i < POW; i++) {
        nodes[node].parents[i] = nodes[nodes[node].parents[i - 1]].parents[i - 1];
    }
    
    int size = 1;
    
    for(int i = 0; i < nodes[node].conns.size(); i++) {
        int child = nodes[node].conns[i];
        if(child != nodes[node].parents[0]) {
            nodes[child].parents[0] = node;
            euler = setup(child, depth + 1, euler, dist);
            size += nodes[child].subtree_size;
        }
    }
    nodes[node].subtree_size = size;
    return euler;
}
 
void setup_tree(int root) {
    nodes[root].parents[0] = root;
    setup(root, 0, 0, 0);
}
 
int get_subtree_depth(int node) {
    if(nodes[node].subtree_depth)
        return nodes[node].subtree_depth;
    
    int max_depth = 1;
    for(int child : nodes[node].conns) {
        if(child == nodes[node].parents[0])
            continue;
        max_depth = max(max_depth, get_subtree_depth(child) + 1);
    }
    nodes[node].subtree_depth = max_depth;
    return max_depth;
}
 
int get_parent(int node, int depth) {
    if(depth > nodes[node].depth)
        return -1;
    
    int climber = node;
    for(int i = 0; i < POW; i++) {
        if(depth & (1 << i) && climber != -1)
            climber = nodes[climber].parents[i];
    }
    
    return climber;
}

bool is_sub(int a,int b){
    return get_parent(a,nodes[a].depth-nodes[b].depth)==b;
}
 
int lca(int a, int b) {
    if(nodes[a].depth < nodes[b].depth)
        swap(a, b);
    
    a = get_parent(a, nodes[a].depth - nodes[b].depth);
    
    if(a == b)
        return a;
    
    for(int i = POW - 1; i >= 0; i--) {
        if(nodes[a].parents[i] != nodes[b].parents[i]) {
            a = nodes[a].parents[i];
            b = nodes[b].parents[i];
        }
    }
    
    return nodes[a].parents[0];
}
 
#endif
 
#ifdef DSU
 
class Dsu {
    vector<int> arr;
    int num_sets;
    
public:
    Dsu(int size) {
        arr = vector<int>(size, -1);
        num_sets = size;
    }
    
    int merge(int a, int b) {
        a = get(a);
        b = get(b);
        
        if(a == b)
            return a;
        
        if(arr[a] > arr[b])
            swap(a, b);
        
        arr[a] += arr[b];
        arr[b] = a;
        num_sets--;
        return a;
    }
    
    int get(int a) {
        if(arr[a] < 0)
            return a;
        arr[a] = get(arr[a]);
        return get(arr[a]);
    }
    
    int get_size(int a) {
        return -arr[get(a)];
    }
    
    int get_num_sets() {
        return num_sets;
    }
};
 
#endif
 
#ifdef MATH
 
ll dpf[2000001];
ll factorial(ll n) {
    if(n == 0)
        return 1;
    
    if(dpf[n])
        return dpf[n];
    
    ll result = factorial(n - 1) * n;
    result %= MOD;
    dpf[n] = result;
    return result;
}
 
ll powm(ll base, ll exp) {
    ll result = 1;
    
    for(int i = 0; i < 64; i++) {
        if((exp >> i) % 2 == 1) {
            result *= base;
            result %= MOD;
        }
        base *= base;
        base %= MOD;
    }
    
    return result;
}
 
ll inverse(ll n) {
    return powm(n, MOD - 2);
}
 
ll dpif[2000001];
ll inverse_factorial(ll n) {
    if(dpif[n])
        return dpif[n];
    
    ll result = inverse(factorial(n));
    dpif[n] = result;
    return result;
}
 
ll choose(ll n, ll k) {
    return (((factorial(n)*inverse_factorial(n-k))%MOD)*inverse_factorial(k))%MOD;
}
 
ll gcd(ll a, ll b){
    if(a==b)
        return a;
    if(a<b)
        swap(a,b);
    if(b==0)
        return a;
    return gcd(b, a%b);
}
 
#endif

const ll MOD2=998244353;
const int NUM_SYMBOLS=62;
int char_to_int(char c){
    if('a'<=c&&c<='z')
        return c-'a';
    if('A'<=c&&c<='Z')
        return c-'A'+('z'-'a'+1);
    return c-'0'+('z'-'a'+1)+('Z'-'A'+1);
}

bool is_pal(string str){
    string rstr=str;
    reverse(rstr.begin(),rstr.end());
    return str==rstr;
}

ll counts[NUM_SYMBOLS][NUM_SYMBOLS];
ll dp[NUM_SYMBOLS][NUM_SYMBOLS][NUM_SYMBOLS];

int main(){
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    
    //freopen("speeding.in","r",stdin);
    //freopen("speeding.out","w",stdout);
    
    int n;
    cin>>n;
    vector<string>strs(n);
    for(int i=0;i<n;i++){
        cin>>strs[i];
        string rev=strs[i];
        reverse(rev.begin(),rev.end());
        if(strs[i]>rev)
            strs[i]=rev;
    }
    set<string>s(strs.begin(),strs.end());
    strs={s.begin(),s.end()};
    vector<pair<char,char>>arr[11];
    for(string str:strs){
        int l=(int)str.size();
        if(is_pal(str)){
            arr[l].emplace_back(str[0],str[0]);
        }else{
            arr[l].emplace_back(str[0],str.back());
            if(str[0]==str.back())
                arr[l].emplace_back(str[0],str.back());
        }
    }
    
    ll res=0;
    for(int i=3;i<=10;i++){
        memset(counts,0,NUM_SYMBOLS*NUM_SYMBOLS*sizeof(ll));
        for(auto p:arr[i]){
            char c1=p.first;
            char c2=p.second;
            counts[char_to_int(c1)][char_to_int(c2)]++;
            if(c1!=c2)
                counts[char_to_int(c2)][char_to_int(c1)]++;
        }
        
#define ITER(c,to) for(int c=0;c<to;c++)
        
        memset(dp,0,sizeof(dp));
        
        ITER(c1,NUM_SYMBOLS){
            ITER(c2,c1+1){
                ITER(c3,c2+1){
                    ITER(c4,NUM_SYMBOLS){
                        dp[c1][c2][c3]+=(counts[c1][c4]*counts[c2][c4])%MOD2*counts[c3][c4];
                        dp[c1][c2][c3]%=MOD2;
                    }
                }
            }
        }
        
        ITER(c1,NUM_SYMBOLS){
            ITER(c2,c1+1){
                ITER(c3,c2+1){
                    ITER(c4,c3+1){
                        ll mul=0;
                        int s=(c1==c2)+(c2==c3)+(c3==c4);
                        if(s==0){
                            mul=24;
                        }else if(s==1){
                            mul=12;
                        }else if(s==2&&c2!=c3){
                            mul=6;
                        }else if(s==2){
                            mul=4;
                        }else if(s==3){
                            mul=1;
                        }
                        
                        res+=(((mul*dp[c1][c2][c3])%MOD2*dp[c1][c2][c4]%MOD2)*dp[c1][c3][c4]%MOD2)*dp[c2][c3][c4];
                        res%=MOD2;
                    }
                }
            }
        }
    }
    
    cout<<res<<"\n";
    
    return 0;
}

/*
 
 
3
bac
bad
cad
 
 */

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 14400 KB Output is correct
2 Correct 151 ms 14432 KB Output is correct
3 Correct 153 ms 14412 KB Output is correct
4 Correct 150 ms 14432 KB Output is correct
5 Correct 146 ms 14484 KB Output is correct
6 Correct 145 ms 14412 KB Output is correct
7 Correct 150 ms 14448 KB Output is correct
8 Correct 145 ms 14496 KB Output is correct
9 Correct 145 ms 14420 KB Output is correct
10 Correct 146 ms 14412 KB Output is correct
11 Correct 147 ms 14376 KB Output is correct
12 Correct 146 ms 14444 KB Output is correct
13 Correct 145 ms 14412 KB Output is correct
14 Correct 148 ms 14368 KB Output is correct
15 Correct 146 ms 14412 KB Output is correct
16 Correct 146 ms 14356 KB Output is correct
17 Correct 145 ms 14420 KB Output is correct
18 Correct 147 ms 14412 KB Output is correct
19 Correct 145 ms 14440 KB Output is correct
20 Correct 149 ms 14404 KB Output is correct
21 Correct 151 ms 14392 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 14400 KB Output is correct
2 Correct 151 ms 14432 KB Output is correct
3 Correct 153 ms 14412 KB Output is correct
4 Correct 150 ms 14432 KB Output is correct
5 Correct 146 ms 14484 KB Output is correct
6 Correct 145 ms 14412 KB Output is correct
7 Correct 150 ms 14448 KB Output is correct
8 Correct 145 ms 14496 KB Output is correct
9 Correct 145 ms 14420 KB Output is correct
10 Correct 146 ms 14412 KB Output is correct
11 Correct 147 ms 14376 KB Output is correct
12 Correct 146 ms 14444 KB Output is correct
13 Correct 145 ms 14412 KB Output is correct
14 Correct 148 ms 14368 KB Output is correct
15 Correct 146 ms 14412 KB Output is correct
16 Correct 146 ms 14356 KB Output is correct
17 Correct 145 ms 14420 KB Output is correct
18 Correct 147 ms 14412 KB Output is correct
19 Correct 145 ms 14440 KB Output is correct
20 Correct 149 ms 14404 KB Output is correct
21 Correct 151 ms 14392 KB Output is correct
22 Correct 164 ms 14808 KB Output is correct
23 Correct 146 ms 14796 KB Output is correct
24 Correct 156 ms 14748 KB Output is correct
25 Correct 145 ms 14800 KB Output is correct
26 Correct 155 ms 14736 KB Output is correct
27 Correct 148 ms 14744 KB Output is correct
28 Correct 146 ms 14760 KB Output is correct
29 Correct 149 ms 14796 KB Output is correct
30 Correct 156 ms 14764 KB Output is correct
31 Correct 148 ms 14764 KB Output is correct
32 Correct 147 ms 14736 KB Output is correct
33 Correct 146 ms 14796 KB Output is correct
34 Correct 155 ms 14768 KB Output is correct
35 Correct 147 ms 14844 KB Output is correct
36 Correct 151 ms 14852 KB Output is correct
37 Correct 153 ms 14768 KB Output is correct
38 Correct 147 ms 14744 KB Output is correct
39 Correct 146 ms 14828 KB Output is correct
40 Correct 149 ms 14844 KB Output is correct
41 Correct 151 ms 14748 KB Output is correct
42 Correct 146 ms 14796 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 14400 KB Output is correct
2 Correct 151 ms 14432 KB Output is correct
3 Correct 153 ms 14412 KB Output is correct
4 Correct 150 ms 14432 KB Output is correct
5 Correct 146 ms 14484 KB Output is correct
6 Correct 145 ms 14412 KB Output is correct
7 Correct 150 ms 14448 KB Output is correct
8 Correct 145 ms 14496 KB Output is correct
9 Correct 145 ms 14420 KB Output is correct
10 Correct 146 ms 14412 KB Output is correct
11 Correct 147 ms 14376 KB Output is correct
12 Correct 146 ms 14444 KB Output is correct
13 Correct 145 ms 14412 KB Output is correct
14 Correct 148 ms 14368 KB Output is correct
15 Correct 146 ms 14412 KB Output is correct
16 Correct 146 ms 14356 KB Output is correct
17 Correct 145 ms 14420 KB Output is correct
18 Correct 147 ms 14412 KB Output is correct
19 Correct 145 ms 14440 KB Output is correct
20 Correct 149 ms 14404 KB Output is correct
21 Correct 151 ms 14392 KB Output is correct
22 Correct 164 ms 14808 KB Output is correct
23 Correct 146 ms 14796 KB Output is correct
24 Correct 156 ms 14748 KB Output is correct
25 Correct 145 ms 14800 KB Output is correct
26 Correct 155 ms 14736 KB Output is correct
27 Correct 148 ms 14744 KB Output is correct
28 Correct 146 ms 14760 KB Output is correct
29 Correct 149 ms 14796 KB Output is correct
30 Correct 156 ms 14764 KB Output is correct
31 Correct 148 ms 14764 KB Output is correct
32 Correct 147 ms 14736 KB Output is correct
33 Correct 146 ms 14796 KB Output is correct
34 Correct 155 ms 14768 KB Output is correct
35 Correct 147 ms 14844 KB Output is correct
36 Correct 151 ms 14852 KB Output is correct
37 Correct 153 ms 14768 KB Output is correct
38 Correct 147 ms 14744 KB Output is correct
39 Correct 146 ms 14828 KB Output is correct
40 Correct 149 ms 14844 KB Output is correct
41 Correct 151 ms 14748 KB Output is correct
42 Correct 146 ms 14796 KB Output is correct
43 Correct 148 ms 14844 KB Output is correct
44 Correct 147 ms 14936 KB Output is correct
45 Correct 153 ms 14928 KB Output is correct
46 Correct 147 ms 14848 KB Output is correct
47 Correct 150 ms 14968 KB Output is correct
48 Correct 149 ms 14964 KB Output is correct
49 Correct 147 ms 14852 KB Output is correct
50 Correct 158 ms 14880 KB Output is correct
51 Correct 148 ms 14872 KB Output is correct
52 Correct 147 ms 14852 KB Output is correct
53 Correct 157 ms 14908 KB Output is correct
54 Correct 147 ms 14924 KB Output is correct
55 Correct 147 ms 14920 KB Output is correct
56 Correct 154 ms 14848 KB Output is correct
57 Correct 153 ms 14952 KB Output is correct
58 Correct 148 ms 14968 KB Output is correct
59 Correct 147 ms 14868 KB Output is correct
60 Correct 153 ms 14912 KB Output is correct
61 Correct 151 ms 14948 KB Output is correct
62 Correct 148 ms 14924 KB Output is correct
63 Correct 149 ms 14888 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 14400 KB Output is correct
2 Correct 151 ms 14432 KB Output is correct
3 Correct 153 ms 14412 KB Output is correct
4 Correct 150 ms 14432 KB Output is correct
5 Correct 146 ms 14484 KB Output is correct
6 Correct 145 ms 14412 KB Output is correct
7 Correct 150 ms 14448 KB Output is correct
8 Correct 145 ms 14496 KB Output is correct
9 Correct 145 ms 14420 KB Output is correct
10 Correct 146 ms 14412 KB Output is correct
11 Correct 147 ms 14376 KB Output is correct
12 Correct 146 ms 14444 KB Output is correct
13 Correct 145 ms 14412 KB Output is correct
14 Correct 148 ms 14368 KB Output is correct
15 Correct 146 ms 14412 KB Output is correct
16 Correct 146 ms 14356 KB Output is correct
17 Correct 145 ms 14420 KB Output is correct
18 Correct 147 ms 14412 KB Output is correct
19 Correct 145 ms 14440 KB Output is correct
20 Correct 149 ms 14404 KB Output is correct
21 Correct 151 ms 14392 KB Output is correct
22 Correct 164 ms 14808 KB Output is correct
23 Correct 146 ms 14796 KB Output is correct
24 Correct 156 ms 14748 KB Output is correct
25 Correct 145 ms 14800 KB Output is correct
26 Correct 155 ms 14736 KB Output is correct
27 Correct 148 ms 14744 KB Output is correct
28 Correct 146 ms 14760 KB Output is correct
29 Correct 149 ms 14796 KB Output is correct
30 Correct 156 ms 14764 KB Output is correct
31 Correct 148 ms 14764 KB Output is correct
32 Correct 147 ms 14736 KB Output is correct
33 Correct 146 ms 14796 KB Output is correct
34 Correct 155 ms 14768 KB Output is correct
35 Correct 147 ms 14844 KB Output is correct
36 Correct 151 ms 14852 KB Output is correct
37 Correct 153 ms 14768 KB Output is correct
38 Correct 147 ms 14744 KB Output is correct
39 Correct 146 ms 14828 KB Output is correct
40 Correct 149 ms 14844 KB Output is correct
41 Correct 151 ms 14748 KB Output is correct
42 Correct 146 ms 14796 KB Output is correct
43 Correct 148 ms 14844 KB Output is correct
44 Correct 147 ms 14936 KB Output is correct
45 Correct 153 ms 14928 KB Output is correct
46 Correct 147 ms 14848 KB Output is correct
47 Correct 150 ms 14968 KB Output is correct
48 Correct 149 ms 14964 KB Output is correct
49 Correct 147 ms 14852 KB Output is correct
50 Correct 158 ms 14880 KB Output is correct
51 Correct 148 ms 14872 KB Output is correct
52 Correct 147 ms 14852 KB Output is correct
53 Correct 157 ms 14908 KB Output is correct
54 Correct 147 ms 14924 KB Output is correct
55 Correct 147 ms 14920 KB Output is correct
56 Correct 154 ms 14848 KB Output is correct
57 Correct 153 ms 14952 KB Output is correct
58 Correct 148 ms 14968 KB Output is correct
59 Correct 147 ms 14868 KB Output is correct
60 Correct 153 ms 14912 KB Output is correct
61 Correct 151 ms 14948 KB Output is correct
62 Correct 148 ms 14924 KB Output is correct
63 Correct 149 ms 14888 KB Output is correct
64 Correct 149 ms 15044 KB Output is correct
65 Correct 157 ms 15044 KB Output is correct
66 Correct 149 ms 15116 KB Output is correct
67 Correct 150 ms 15052 KB Output is correct
68 Correct 147 ms 15104 KB Output is correct
69 Correct 153 ms 15040 KB Output is correct
70 Correct 149 ms 15052 KB Output is correct
71 Correct 148 ms 15100 KB Output is correct
72 Correct 147 ms 15024 KB Output is correct
73 Correct 154 ms 15124 KB Output is correct
74 Correct 148 ms 15088 KB Output is correct
75 Correct 147 ms 15108 KB Output is correct
76 Correct 148 ms 14992 KB Output is correct
77 Correct 158 ms 15052 KB Output is correct
78 Correct 151 ms 15080 KB Output is correct
79 Correct 150 ms 15052 KB Output is correct
80 Correct 163 ms 15040 KB Output is correct
81 Correct 150 ms 15096 KB Output is correct
82 Correct 145 ms 15104 KB Output is correct
83 Correct 151 ms 15008 KB Output is correct
84 Correct 154 ms 15004 KB Output is correct