# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
334573 | doowey | Parametriziran (COCI19_parametriziran) | C++14 | 224 ms | 15212 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int M = 6;
const int AL = 27;
const int N = 50005;
vector<int> ind[1<<M];
int f[M];
string s[N];
int vl[N][1<<M];
int main(){
fastIO;
int n, m;
cin >> n >> m;
f[0]=1;
for(int i = 1; i < M ; i ++) {
f[i]=(f[i-1]*AL);
}
int que;
int sln;
for(int i = 0 ; i < n; i ++ ){
cin >> s[i];
que = 0;
for(int j = 0 ; j < m ; j ++ ){
if(s[i][j] == '?') que |= (1 << j);
}
ind[que].push_back(i);
for(int mm = 0 ; mm < (1 << m); mm ++ ){
if((mm & que) != que) continue;
sln = 0;
for(int j = 0 ; j < m ; j ++ ){
if((mm & (1 << j))) continue;
sln += f[j] * 1ll * (s[i][j] - 'a' + 1);
}
vl[i][mm]=sln;
}
}
ll soln = 0;
vector<int> ay, by;
int mask;
int jj,c1,c2;
for(int p = 0 ; p < (1 << m); p ++ ){
for(int q = p + 1 ; q < (1 << m) ; q ++ ){
if(ind[p].empty() || ind[q].empty()) continue;
mask = (p | q);
ay.clear();
by.clear();
for(auto x : ind[p]){
ay.push_back(vl[x][mask]);
}
for(auto x : ind[q]){
by.push_back(vl[x][mask]);
}
sort(ay.begin(), ay.end());
sort(by.begin(), by.end());
jj = 0;
c1 = 0;
for(int i = 0 ; i < ay.size(); i ++ ){
c1 ++ ;
if(i + 1 == ay.size() || ay[i] != ay[i + 1]){
c2 = 0;
while(jj < by.size() && by[jj] <= ay[i]){
if(by[jj] == ay[i]){
c2 ++ ;
}
jj ++ ;
}
soln += c1 * 1ll * c2;
c1 = 0;
}
}
}
}
cout << soln << "\n";
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |