Submission #96661

#	Time	Username	Problem	Language	Result	Execution time	Memory
96661		noneTP	Parametriziran (COCI19_parametriziran)	C++14	110 / 110	2307 ms	42820 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef tuple<int, int, int> tp;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
typedef pair<LL, LL> pll;
typedef pair<pii, int> piipi;
typedef pair<int, pii> pipii;
typedef pair<pii, pii> piipii;
typedef pair<LL, pii> plpii;
typedef pair<LD, LD> pdd;
typedef pair<LD, int> pdi;
typedef pair<LD, LL> pdl;
typedef pair<int, LD> pid;
typedef pair<LL, LD> pld;
const int mod = 1e9 + 7;
const int hf = 999983;
const int N = 1e6;

int hv[10];
char s[10];
map<int, int> dp[64][64];
int main(){
    LL ans = 0;
    hv[0] = 1;
    for(int i=1;i<10;i++) hv[i] = (hv[i-1]*1ll*hf)%mod;
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++){
        scanf("%s", s);
        int b = 0;
        for(int j=0;j<m;j++){
            if(s[j] == '?') b+=(1<<j);
        }
        for(int j=0;j<(1<<m);j++){
            int c = (b|j), val = 0;
            for(int k=0;k<m;k++){
                if((c>>k)&1) continue;
                val = (val + hv[k]*1ll*s[k])%mod;
            }
            c ^= j;
            if(dp[j][c].count(val)) ans = (ans + dp[j][c][val]);
        }
        vector<int> v;
        int x = (1<<m)-1 - b;
        for(int j=0;j<m;j++){
            if((x>>j)&1) v.push_back(j);
        }
        int sz = v.size();
        for(int j=0;j<(1<<sz);j++){
            int c = 0, val = 0;
            for(int k=0;k<sz;k++){
                if((j>>k)&1) c |= (1<<v[k]);
                else val = (val + hv[v[k]]*1ll*s[v[k]])%mod;
            }
            dp[b][c][val]++;
        }
    }
    printf("%lld\n", ans);
}

Compilation message (stderr)

parametriziran.cpp: In function 'int main()':
parametriziran.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
parametriziran.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", s);
         ~~~~~^~~~~~~~~

• 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