Submission #717648

#	Time	Username	Problem	Language	Result	Execution time	Memory
717648		TheSahib	Set (COCI21_set)	C++17	40 / 110	1081 ms	24092 KiB

Main

#include <bits/stdc++.h>

#define ll long long
#define oo 1e9
#define pii pair<int, int>

using namespace std;

const int MAX = 2e6;

int n, k;


bool arr[MAX];

int hashString(string s){
    int a = 0;
    int b = 1;
    for (int i = s.size() - 1; i >= 0; i--)
    {
        a += (s[i] - '1') * b;
        b *= 3;
    }
    return a;
}

void solve(){
    cin >> n >> k;
    string cards[n];
    for (int i = 0; i < n; i++)
    {
        cin >> cards[i];
        arr[hashString(cards[i])] = true;
    }
    ll ans = 0;
    for(string s:cards){
        char others[k][2];
        for (int i = 0; i < k; i++)
        {
            if(s[i] == '1'){
                others[i][0] = '2';
                others[i][1] = '3';
            }
            if(s[i] == '2'){
                others[i][0] = '1';
                others[i][1] = '3';
            }
            if(s[i] == '3'){
                others[i][0] = '1';
                others[i][1] = '2';
            }
        }
        
        
        for (int mask = 1; mask < (1 << k); mask++)
        {
            for (int subMask = mask; subMask >= 0; subMask = (subMask - 1) & mask)
            {
                string a, b;
                for (int i = 0; i < k; i++)
                {
                    if(!(mask & (1 << i))){
                        a += s[i];
                        b += s[i];
                    }
                    else if(subMask & (1 << i)){
                        a += others[i][1];
                        b += others[i][0];
                    }
                    else{
                        a += others[i][0];
                        b += others[i][1];
                    }
                }
                ans += (arr[hashString(a)] & arr[hashString(b)]);
                if(subMask == 0) break;
            }
        }
    }
    cout << ans / 6 << '\n';
}

int main()
{
    solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 0 / 70