oj.uz

Submission #104551

# Submission time Handle Problem Language Result Execution time Memory
104551 2019-04-07T22:31:46 Z Hassoony Parametriziran (COCI19_parametriziran) C++17
0 / 110
 1490 ms 47912 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];
unordered_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]++;
        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+='?';
        }
//        cout<<tmp<<" "<<vis[i].size()<<endl;
        if(sum)ret+=vis1[i]-vis[i].count(tmp);
        else ret-=(vis1[i]-vis[i].count(tmp));
    }
//    cout<<ret<<endl;
    return ret;
}
int main(){
    cin>>n>>m;ans=(n*(n-1))/2;
    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: In function 'll get(std::__cxx11::string)':
parametriziran.cpp:31:19: warning: unused variable 'ok1' [-Wunused-variable]
         bool ok=1,ok1=1;
                   ^~~
parametriziran.cpp: In function 'int main()':
parametriziran.cpp:55:23: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[8]' [-Wformat=]
         scanf("%s",&oo);s=oo;
                    ~~~^
parametriziran.cpp:55: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 14 ms 384 KB Output isn't correct

Subtask #2
0 / 11.0

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

Subtask #3
0 / 11.0

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

Subtask #4
0 / 11.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 11.0

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

Subtask #7
0 / 11.0

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

Subtask #8
0 / 11.0

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

Subtask #9
0 / 11.0

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

Subtask #10
0 / 11.0

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