Submission #369202

#TimeUsernameProblemLanguageResultExecution timeMemory
369202idontreallyknowParametriziran (COCI19_parametriziran)C++14
0 / 110
52 ms65540 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; mt19937/*_64*/ rng(chrono::steady_clock::now().time_since_epoch().count()); #define printArr(arr, n) cerr << #arr << " = ["; for(int i=0; i<(n); i++){if (i) cerr << ", "; cerr << arr[i];} cerr << "]\n" template<class A> ostream& operator<<(ostream &cout, vector<A> const &v) {cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";}; template<class A, class B> ostream& operator<<(ostream &cout, const pair<A,B> &x) {return cout << "(" <<x.first << ", " << x.second << ")";}; void _print() {cerr << "]\n";} template <class T, class... V> void _print(T t, V... v) {cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);} #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #define fi first #define se second #define SZ(x) (int)((x).size()) #define pii pair<int,int> struct TrieAlpha { vector<array<int,27>> nxt; vector<int> sz; int en = 0; TrieAlpha(int x) : nxt(x), sz(x) {} void update(string s, int ct) //change ct for add/remove { int cur = 0; sz[cur] += ct; for (int q = SZ(s)-1; q >= 0; q--) { int t = s[q]-'a'; if (!nxt[cur][t]) nxt[cur][t] = ++en; sz[cur=nxt[cur][t]] += ct; } } int contains(string s) { int cur = 0; for (int q = SZ(s)-1; q >= 0; q--) { int t = s[q]-'a'; if (!nxt[cur][t]) return 0; cur = nxt[cur][t]; } return sz[cur]; } }; TrieAlpha tr(6200000); int amt[64]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n,m; cin >> n >> m; string s; string t = ""; for (int q = 0; q < m; q++) t.push_back('{'); ll tot = 0; for (int q = 0; q < n; q++) { cin >> s; for (int w = 1; w < (1<<m); w++) { bool bad = false; string ss = t; for (int e = 0; e < m; e++) { if (((1<<e)&w) > 0) { if (s[e] == '?') bad = true; else ss[e] = s[e]; } } if (bad) continue; tot += (__builtin_popcount(w) % 2 ? 1 : -1 ) * amt[w]-tr.contains(ss); tr.update(ss,1); amt[w]++; } } cout << (ll)n*(n-1)/2 - tot << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...