oj.uz

Submission #1040819

# Submission time Handle Problem Language Result Execution time Memory
1040819 2024-08-01T10:03:13 Z anton Cubeword (CEOI19_cubeword) C++17
21 / 100
 1100 ms 21672 KB 
#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>

const int MOD = 998244353LL;
const int MAX_N =16LL;
int nbP[MAX_N][MAX_N];
int mid[MAX_N][MAX_N][MAX_N][MAX_N];
int RES = 0;

vector<pii> cube_edges = {
{0, 1},
{1, 2},
{2, 3},
{3, 0},
{4, 5},
{5, 6},
{6, 7},
{7, 4},
{0, 4},
{1, 5}, 
{2, 6},
{3, 7},
};


bool is_palindrome(string s){
    bool ok = true;
    for(int i = 0; i<(s.size()+1)/2; i++){
        ok &= (s[i] == s[s.size()-i-1]);
    }
    return ok;
}

int mexp(int a, int b){
    int res = 1;
    vector<int>pows(1, a);


    for(int i= 1; i<35; i++){
        pows.push_back((pows.back()*pows.back())%MOD);
    }
    
    for(int i = 0; i<35; i++){
        if(0LL!=((1LL<<i)&b)){
            res = (res * pows[i])%MOD;
        }
    }

    return res;
}

unordered_map<int, int> inv;
int modinv(int a){
    if(inv.find(a)!=inv.end()){
        return inv[a];
    }
    int b= mexp(a, MOD-2);
    inv[a] = b;
    assert((a*b)%MOD == 1);
    return b;
}
vector<pair<int, vector<int>>> iterate_all(int nbSteps, int maxC){
    vector<int> cur = vector<int>(nbSteps, 0);
    vector<pair<int, vector<int>>> res;

    bool ok = true;

    for(int first_v = 0; first_v <maxC; first_v++){
        cur =vector<int>(nbSteps, 0);
        cur[0] = first_v;
        ok =true;
        while(ok){
            cur.back()++;
            for(int i = nbSteps-1; i>1; i--){
                if(cur[i]>first_v){
                    cur[i-1]++;
                    cur[i] = 0;
                }
            }

            if(cur[1] >first_v){
                ok = false;
                cur[1] = 0;
            }
            int nb_same = 0;
            for(auto e: cur){
                if(e == first_v){
                    nb_same++;
                }
            }
            res.push_back({nbSteps * modinv(nb_same), cur});
        }
        

    }
    return res;
}

vector<pair<int, vector<int>>> all(int len, int base){
    vector<int> cur = vector<int>(len, 0);
    vector<pair<int, vector<int>>> res;

    bool ok = true;


    while(ok){
        cur.back()++;
        for(int i = len-1; i>0; i--){
            if(cur[i]>=base){
                cur[i-1]++;
                cur[i] = 0;
            }
        }

        if(cur[0] >=base){
            ok = false;
            cur[0] = 0;
        }
        res.push_back({1, cur});
    }
    return res;
}


vector<pair<int, vector<int>>> all_weighted(int len, int base){
    vector<int> cur = vector<int>(len, 0);
    vector<pair<int, vector<int>>> res;

    bool ok = true;


    while(ok){
        cur.back()++;
        for(int i = len-1; i>0; i--){
            if(cur[i]>=base){
                cur[i-1]++;
                cur[i] = 0;
            }
        }

        if(cur[0] >=base){
            ok = false;
            cur[0] = 0;
        }
        res.push_back({1, cur});
    }

    for(pair<int, vector<int>>& e: res){
        int oc= 1;
        for(int i = 0; i<4; i++){
            auto edge = cube_edges[i];
            oc =(oc * nbP[e.second[edge.first]][e.second[edge.second]])%MOD;
        }
        e.first = oc;
    }
    return res;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin>>N;
    vector<set<string>> words(11);

    for(int i = 0; i<N; i++){
        string s;
        cin>>s;
        if(is_palindrome(s)){
            words[s.size()].insert(s);
        }
        else{
            words[s.size()].insert(s);
            reverse(s.begin(), s.end());
            words[s.size()].insert(s);
        }
    }

    //vector<pair<int, vector<int>>> colorings=  iterate_all(8,6);
    for(int len = 3; len<=10; len++){
        fill(&nbP[0][0], &nbP[MAX_N][0], 0);
        fill(&mid[0][0][0][0], &mid[MAX_N][0][0][0], 0);

        for(auto e: words[len]){
            int a=  e[0]-'a';
            int b= e.back()-'a';
            nbP[a][b]++;
        }
        vector<pair<int, vector<int>>> colorings=  all_weighted(4,MAX_N);


        for(auto e: colorings){
            if(e.first>0){
            /*cout<<"starting from "<<endl;
            for(auto c: e.second){
                cout<<c<<" ";
            }
            cout<<endl;*/
            int i= 0;
            for(auto f: all(2, MAX_N)){
                pii up = {f.second[0], f.second[1]};
                //cout<<up.first<<" "<<up.second<<endl;
                mid[up.first][up.second][e.second[2]][e.second[3]] = (mid[up.first][up.second][e.second[2]][e.second[3]] + ((nbP[e.second[0]][up.first]*nbP[e.second[1]][up.second])%MOD * e.first)%MOD)%MOD;
                //cout<<up.first<<" "<<up.second<<" "<<e.second[2]<<" "<<e.second[3]<<" "<<mid[up.first][up.second][e.second[2]][e.second[3]]<<endl;
            } 
            } 
        }


        for(auto e: colorings){
            auto v = e.second;
            RES = (RES + (mid[v[0]][v[1]][v[2]][v[3]] * mid[v[3]][v[2]][v[1]][v[0]])%MOD)%MOD;
        }
    }

    cout<<RES<<endl;
}

Compilation message

cubeword.cpp: In function 'bool is_palindrome(std::string)':
cubeword.cpp:31:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i = 0; i<(s.size()+1)/2; i++){
      |                    ~^~~~~~~~~~~~~~~
cubeword.cpp: In function 'int main()':
cubeword.cpp:202:17: warning: unused variable 'i' [-Wunused-variable]
  202 |             int i= 0;
      |                 ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 21392 KB Output is correct
2 Correct 244 ms 21584 KB Output is correct
3 Correct 245 ms 21416 KB Output is correct
4 Correct 257 ms 21484 KB Output is correct
5 Correct 254 ms 21556 KB Output is correct
6 Correct 238 ms 21524 KB Output is correct
7 Correct 257 ms 21472 KB Output is correct
8 Correct 242 ms 21604 KB Output is correct
9 Correct 243 ms 21420 KB Output is correct
10 Correct 251 ms 21536 KB Output is correct
11 Correct 250 ms 21420 KB Output is correct
12 Correct 258 ms 21672 KB Output is correct
13 Correct 247 ms 21416 KB Output is correct
14 Correct 233 ms 21604 KB Output is correct
15 Correct 244 ms 21416 KB Output is correct
16 Correct 241 ms 21416 KB Output is correct
17 Correct 257 ms 21420 KB Output is correct
18 Correct 251 ms 21400 KB Output is correct
19 Correct 247 ms 21584 KB Output is correct
20 Correct 245 ms 21504 KB Output is correct
21 Correct 242 ms 21548 KB Output is correct

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 21392 KB Output is correct
2 Correct 244 ms 21584 KB Output is correct
3 Correct 245 ms 21416 KB Output is correct
4 Correct 257 ms 21484 KB Output is correct
5 Correct 254 ms 21556 KB Output is correct
6 Correct 238 ms 21524 KB Output is correct
7 Correct 257 ms 21472 KB Output is correct
8 Correct 242 ms 21604 KB Output is correct
9 Correct 243 ms 21420 KB Output is correct
10 Correct 251 ms 21536 KB Output is correct
11 Correct 250 ms 21420 KB Output is correct
12 Correct 258 ms 21672 KB Output is correct
13 Correct 247 ms 21416 KB Output is correct
14 Correct 233 ms 21604 KB Output is correct
15 Correct 244 ms 21416 KB Output is correct
16 Correct 241 ms 21416 KB Output is correct
17 Correct 257 ms 21420 KB Output is correct
18 Correct 251 ms 21400 KB Output is correct
19 Correct 247 ms 21584 KB Output is correct
20 Correct 245 ms 21504 KB Output is correct
21 Correct 242 ms 21548 KB Output is correct
22 Execution timed out 1172 ms 21284 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 21392 KB Output is correct
2 Correct 244 ms 21584 KB Output is correct
3 Correct 245 ms 21416 KB Output is correct
4 Correct 257 ms 21484 KB Output is correct
5 Correct 254 ms 21556 KB Output is correct
6 Correct 238 ms 21524 KB Output is correct
7 Correct 257 ms 21472 KB Output is correct
8 Correct 242 ms 21604 KB Output is correct
9 Correct 243 ms 21420 KB Output is correct
10 Correct 251 ms 21536 KB Output is correct
11 Correct 250 ms 21420 KB Output is correct
12 Correct 258 ms 21672 KB Output is correct
13 Correct 247 ms 21416 KB Output is correct
14 Correct 233 ms 21604 KB Output is correct
15 Correct 244 ms 21416 KB Output is correct
16 Correct 241 ms 21416 KB Output is correct
17 Correct 257 ms 21420 KB Output is correct
18 Correct 251 ms 21400 KB Output is correct
19 Correct 247 ms 21584 KB Output is correct
20 Correct 245 ms 21504 KB Output is correct
21 Correct 242 ms 21548 KB Output is correct
22 Execution timed out 1172 ms 21284 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 21392 KB Output is correct
2 Correct 244 ms 21584 KB Output is correct
3 Correct 245 ms 21416 KB Output is correct
4 Correct 257 ms 21484 KB Output is correct
5 Correct 254 ms 21556 KB Output is correct
6 Correct 238 ms 21524 KB Output is correct
7 Correct 257 ms 21472 KB Output is correct
8 Correct 242 ms 21604 KB Output is correct
9 Correct 243 ms 21420 KB Output is correct
10 Correct 251 ms 21536 KB Output is correct
11 Correct 250 ms 21420 KB Output is correct
12 Correct 258 ms 21672 KB Output is correct
13 Correct 247 ms 21416 KB Output is correct
14 Correct 233 ms 21604 KB Output is correct
15 Correct 244 ms 21416 KB Output is correct
16 Correct 241 ms 21416 KB Output is correct
17 Correct 257 ms 21420 KB Output is correct
18 Correct 251 ms 21400 KB Output is correct
19 Correct 247 ms 21584 KB Output is correct
20 Correct 245 ms 21504 KB Output is correct
21 Correct 242 ms 21548 KB Output is correct
22 Execution timed out 1172 ms 21284 KB Time limit exceeded
23 Halted 0 ms 0 KB -