Submission #96814

#	Time	Username	Problem	Language	Result	Execution time	Memory
96814		ami	Parametriziran (COCI19_parametriziran)	C++14	110 / 110	2245 ms	37556 KiB

Main

#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 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11