제출 #1248037

#제출 시각아이디문제언어결과실행 시간메모리
1248037nqknhtParametriziran (COCI19_parametriziran)C++20
66 / 110
1764 ms99632 KiB
#include <bits/stdc++.h>

#define ll long long
#define fi first
#define se second
#define len(s) (ll) s.size()

const ll I = 1e6 + 9;
const ll Z = 1e9 + 7;

using namespace std;

int st[15], tf = 0, n, m, a[15], b[14], rs = 0;
map<string, int> dem;

string conv()
{
    string rs = "";
    for (int i = 1; i <= m; i++)
        if (b[i] == 0)
            rs = rs + "?";
        else if (b[i] == 27)
            rs = rs + "1";
        else
            rs = rs + (char)(b[i] + 96);
    return rs;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        string p = "";
        tf = 0;
        int omsk = (1 << m) - 1;
        for (int j = 1; j <= m; j++)
        {
            char c;
            cin >> c;
            if (c == '?')
                a[j] = 0;
            else
                a[j] = (int)c - 96;
            if (a[j] != 0)
            {
                tf++;
                st[tf] = j;
                omsk ^= (1 << (j - 1));
            }
        }
        for (int msk = 0; msk < (1 << tf); msk++)
        {
            for (int id = 1; id <= m; id++)
                b[id] = a[id];
            for (int id = 0; id < tf; id++)
            {
                if ((msk & (1 << id)) == 0)
                    continue;
                b[st[id + 1]] = 0;
            }
            for (int bit = omsk;; bit = omsk & (bit - 1))
            {
                for (int tmp = bit; tmp > 0; tmp &= (tmp - 1))
                {
                    int id = __builtin_ctz(tmp) + 1;
                    b[id] = 27;
                }
                rs += dem[conv()];
                for (int tmp = bit; tmp > 0; tmp &= (tmp - 1))
                {
                    int id = __builtin_ctz(tmp) + 1;
                    b[id] = a[id];
                }
                if (bit == 0)
                    break;
            }
        }
        for (int msk = 0; msk < (1 << tf); msk++)
        {
            for (int id = 1; id <= m; id++)
                b[id] = a[id];
            for (int id = 0; id < tf; id++)
            {
                if ((msk & (1 << id)) == 0)
                    b[st[id + 1]] = 27;
            }
            dem[conv()]++;
        }
    }
    cout << rs;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...