oj.uz

Submission #96814

# Submission time Handle Problem Language Result Execution time Memory
96814 2019-02-12T08:43:47 Z ami Parametriziran (COCI19_parametriziran) C++14
110 / 110
 2245 ms 37556 KB 
#include <bits/stdc++.h>
#define sz(c)      int(c.size())
#define rep(i,a,b) for (int i=a; i<(b); ++i)
#define per(i,a,b) for (int i=(b)-1; i>=(a); --i)
using namespace std;
using ll = long long;
using ull = unsigned long long;

int const MAXN=55000;
int N,M;
string words[MAXN];
unordered_map<ull,int> cnt;
int val[512];

ull enc(const string &s) {
	ull res=0;
	rep(i,0,M) {
		res=res*28+val[int(s[i])];
	}
	return res;
}

ll count_pairs(string s) {
	ll res=0;
	string t=s;
	rep(i,0,M) if (s[i]=='?') s[i]='*';
	rep(mask,0,1<<M) {
		rep(i,0,M) t[i]=(mask>>i&1) ? '?' : s[i];
		ull et=enc(t);
		if (cnt.count(et)) res+=cnt[et];
	}
	return res;
}

void add_word(string s) {
	string t=s;
	rep(mask,0,1<<M) {
		bool ok=true;
		rep(i,0,M) {
			if ((mask>>i&1) && s[i]=='?') {
				ok=false;
				break;
			}

			t[i]=(mask>>i&1) ? '*' : s[i];
		}

		if (ok) {
			cnt[enc(t)]++;
		}
	}
}

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cout<<fixed<<setprecision(10);

	memset(val,~0,sizeof(val));
	rep(i,0,26) val['a'+i]=i;
	val['*']=26;
	val['?']=27;

	cin>>N>>M;
	rep(i,0,N) cin>>words[i];

	ll res=0;
	rep(i,0,N) {
// cerr<<count_pairs(words[i])<<endl;
		res += count_pairs(words[i]);
		add_word(words[i]);
	}

	cout<<res<<"\n";
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2176 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2176 KB Output is correct
2 Correct 16 ms 2176 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2264 KB Output is correct
2 Correct 19 ms 2176 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2908 KB Output is correct
2 Correct 23 ms 2424 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2688 KB Output is correct
2 Correct 45 ms 3092 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 6452 KB Output is correct
2 Correct 53 ms 2424 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 10300 KB Output is correct
2 Correct 80 ms 2424 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 747 ms 17360 KB Output is correct
2 Correct 386 ms 9284 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1482 ms 27852 KB Output is correct
2 Correct 151 ms 2552 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2245 ms 37556 KB Output is correct
2 Correct 1210 ms 19892 KB Output is correct