oj.uz

Submission #96661

# Submission time Handle Problem Language Result Execution time Memory
96661 2019-02-10T16:28:20 Z noneTP Parametriziran (COCI19_parametriziran) C++14
110 / 110
 2307 ms 42820 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 504 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 624 KB Output is correct
2 Correct 11 ms 504 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 504 KB Output is correct
2 Correct 27 ms 604 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 1144 KB Output is correct
2 Correct 26 ms 732 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 992 KB Output is correct
2 Correct 53 ms 1500 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 5548 KB Output is correct
2 Correct 78 ms 632 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 9828 KB Output is correct
2 Correct 37 ms 760 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 681 ms 17848 KB Output is correct
2 Correct 311 ms 8384 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1106 ms 28312 KB Output is correct
2 Correct 57 ms 764 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2307 ms 42820 KB Output is correct
2 Correct 1033 ms 21240 KB Output is correct