Submission #96596

#TimeUsernameProblemLanguageResultExecution timeMemory
96596psmaoParametriziran (COCI19_parametriziran)C++14
11 / 110
13 ms1916 KiB
#include <bits/stdc++.h> using namespace std; #define fo(i,s,t) for(int i = s; i <= t; ++ i) #define fd(i,s,t) for(int i = s; i >= t; -- i) #define bf(i,s) for(int i = head[s]; i; i = e[i].next) #define mp make_pair #define fi first #define se second #define pii pair<int,int> #define pb push_back #define VI vector<int> #define sf scanf #define pf printf #define fp freopen #define SZ(x) ((int)(x).size()) #ifdef MPS #define D(x...) printf(x) #else #define D(x...) #endif typedef long long ll; typedef double db; typedef unsigned long long ull; const int inf = 1<<30; const ll INF = 1ll<<60; const db Inf = 1e20; const db eps = 1e-9; void gmax(int &a,int b){a = (a > b ? a : b);} void gmin(int &a,int b){a = (a < b ? a : b);} const int maxn = 50005; map<string,int> cnt; int lastx[27], firx[27], last[27], fir[27]; int n, m; ll ans; string s[maxn]; int main() { #ifdef MPS fp("1.in","r",stdin); fp("1.out","w",stdout); #endif cin.sync_with_stdio(false); cin >> n >> m; fo(i,1,n) cin >> s[i]; if(m == 1) { int num = 0; fo(i,1,n) { if(s[i] == "?") ++ num; else cnt[s[i]] ++; } fo(i,1,n) if(s[i] != "?") ans += cnt[s[i]] - 1 + num; else ans += n - 1; ans /= 2; cout << ans << endl; } else if(m == 2) { int num = 0, a = 0, b = 0; fo(i,1,n) { if(s[i] == "??") ++ num; else if(s[i][0] == '?') {lastx[s[i][1]-'a'+1] ++; ++ a;} else if(s[i][1] == '?') {firx[s[i][0]-'a'+1] ++; ++ b;} else {last[s[i][1]-'a'+1] ++; fir[s[i][0]-'a'+1] ++; cnt[s[i]] ++;} } fo(i,1,n) { if(s[i] == "??") ans += n-1; else if(s[i][0] == '?') ans += b+last[s[i][1]-'a'+1]+num; else if(s[i][1] == '?') ans += a+fir[s[i][0]-'a'+1]+num; else ans += cnt[s[i]]-1+firx[s[i][0]-'a'+1]+lastx[s[i][1]-'a'+1]+num; } cout << ans/2 << endl; } 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...