Submission #104551

#	Time	Username	Problem	Language	Result	Execution time	Memory
104551		Hassoony	Parametriziran (COCI19_parametriziran)	C++17	0 / 110	1490 ms	47912 KiB

Main

#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 (stderr)

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
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 11
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 11
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11