oj.uz

Submission #96713

# Submission time Handle Problem Language Result Execution time Memory
96713 2019-02-11T11:18:10 Z polyfish Parametriziran (COCI19_parametriziran) C++14
99 / 110
 1596 ms 66560 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) {cerr << #x << " = " << x << '\n';}
#define PR(a, n) {cerr << #a << " = "; for (int _=1; _<=n; ++_) cerr << a[_] << ' '; cerr << '\n';}
#define PR0(a, n) {cerr << #a << " = "; for (int _=0; _<n; ++_) cerr << a[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"
 
const int M = 6;        ///notice
const int MAX_N = 50002;
 
int n;
string s[MAX_N];
vector<int> p(M);
int64_t res, H;
map<int64_t, int> mp;
 
void readInput() {
    int m;
 
    cin >> n >> m;
 
    for (int i=1; i<=n; ++i) {
        cin >> s[i];
        while (s[i].size()<M)
            s[i] += '?';
    }
}
 
void backtrack1(int idx, int pos) {
    if (s[idx][pos]=='?') {
        int64_t tmp = H;
        H = H * 30 + 28;
        if (pos==M-1) {
            // PR0(p, p.size());
            if (mp.count(H))
                res += mp[H];
        }
        else {
            backtrack1(idx, pos+1);
        }
        H = tmp;
    }
    else {
        for (int i=0; i<2; ++i) {
            int64_t tmp = H;
            H = H * 30 + (i==0 ? s[idx][pos]-'a'+1 : 27);
            if (pos==M-1) {
                // PR0(p, p.size());
                if (mp.count(H))
                    res += mp[H];
            }
            else {
                backtrack1(idx, pos+1);
            }
            H = tmp;
        }
    }
}
 
void backtrack2(int idx, int pos) {
    for (int i=0; i<2; ++i) {
        int64_t tmp = H;
        if (i==0)
            H = H * 30 + 28;
        else
            H = H * 30 + (s[idx][pos]=='?' ? 27 : s[idx][pos]-'a'+1);
        if (pos==M-1) {
            // PR0(p, p.size());
            ++mp[H];
        }
        else {
            backtrack2(idx, pos+1);
        }
        H = tmp;
    }
}
 
void solve() {
    for (int i=1; i<=n; ++i) {
        backtrack1(i, 0);
        backtrack2(i, 0);
    }
 
    cout << res;
}
 
int main() {
    #ifdef GLASSES_GIRL
        freopen(FILE_NAME".inp", "r", stdin);
        freopen(FILE_NAME".out", "w", stdout);
    #endif
    readInput();
    solve();
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 1912 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 2796 KB Output is correct
2 Correct 116 ms 2812 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 2680 KB Output is correct
2 Correct 240 ms 2716 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 9228 KB Output is correct
2 Correct 184 ms 4728 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 7416 KB Output is correct
2 Correct 247 ms 9468 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 988 ms 29164 KB Output is correct
2 Correct 233 ms 5164 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 938 ms 33948 KB Output is correct
2 Correct 193 ms 5496 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1304 ms 52044 KB Output is correct
2 Correct 795 ms 29208 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1283 ms 47524 KB Output is correct
2 Correct 242 ms 6008 KB Output is correct

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1596 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -