oj.uz

Submission #104550

# Submission time Handle Problem Language Result Execution time Memory
104550 2019-04-07T21:58:01 Z Hassoony Parametriziran (COCI19_parametriziran) C++17
0 / 110
 2444 ms 51580 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mod=(1e9+7);
const ll inf=(1ll<<61);
const int MX=50009;
int n,m,vis1[MX];
map<string,int>vis[(1<<7)];
string s;
char oo[8];
ll ans=0;
void add(string s){
    for(int j=1;j<(1<<m);j++){
        int ret=0;
        string tmp="";
        bool ok=1;
        for(int i=0;i<s.size();i++){
            if((j&(1<<i)) && s[i]=='?')ok=0;
            if((j&(1<<i)))ret+=(1<<i),tmp+=s[i];
            else tmp+='?';
        }
        if(!ok)continue;
        vis[ret][tmp]++;
    }
    int ret=0;
    for(int i=0;i<s.size();i++){
        if(s[i]!='?')ret+=(1<<i);
    }
    vis1[ret]++;
}
ll get(string s){
    ll ret=0;
    for(int i=0;i<(1<<m);i++){
        bool ok=1,ok1=1;
        int sum=0;
        for(int j=0;j<m;j++){
            bool b=(bool)((i&(1<<j)));
            if(b&&s[j]=='?')ok=0;
            sum^=b;
        }
        if(!ok)continue;
        string tmp="";
        for(int j=0;j<m;j++){
            bool b=(bool)((i&(1<<j)));
            if(b)tmp+=s[j];
            else tmp+='?';
        }
        if(sum)ret+=vis[i].count(tmp);
        else ret-=vis[i].count(tmp);
    }
    for(int i=0;i<(1<<m);i++){
        bool ok=1;
        for(int j=0;j<m;j++){
            bool b=(bool)((i&(1<<j)));
            if(b&&s[j]!='?')ok=0;
        }
        if(ok)ret+=vis1[i];
    }
    return ret;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        scanf("%s",&oo);s=oo;
        ans+=get(s);
        add(s);
    }
    cout<<ans<<endl;
}
/*
3 3
??b
c??
c?c
4 6
ab??c?
??kll?
a?k??c
?bcd??
5 2
??
b?
c?
?g
cg
*/

Compilation message

parametriziran.cpp: In function 'void add(std::__cxx11::string)':
parametriziran.cpp:18:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<s.size();i++){
                     ~^~~~~~~~~
parametriziran.cpp:27:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<s.size();i++){
                 ~^~~~~~~~~
parametriziran.cpp: In function 'll get(std::__cxx11::string)':
parametriziran.cpp:35:19: warning: unused variable 'ok1' [-Wunused-variable]
         bool ok=1,ok1=1;
                   ^~~
parametriziran.cpp: In function 'int main()':
parametriziran.cpp:65:23: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[8]' [-Wformat=]
         scanf("%s",&oo);s=oo;
                    ~~~^
parametriziran.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",&oo);s=oo;
         ~~~~~^~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 384 KB Output isn't correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 1412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 1244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 319 ms 7068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 440 ms 11036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1050 ms 23956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1809 ms 36572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2444 ms 51580 KB Output isn't correct
2 Halted 0 ms 0 KB -