Submission #11206860


Source Code Expand

Copy
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
using namespace std::chrono;
long long int p=1e9 +7;
int n;
bool compatibility[21][21];
ll ans[21][1ll<<21];
ll solve(int N,int left){
    ll currans=0;//initialise with 0
    if(ans[N-1][left]!=-1){//check if we have already found the answer
        return ans[N-1][left];
    }
    if(N==1){
        for(int j=0;j<n;j++){
            int x=1<<j;
            if(left & x){//check if the jth women is left
                if(compatibility[N-1][j]){ 
                    ans[N-1][left]=1;
                    return 1;//If they are compatible return 1
                }
                else{
                    ans[N-1][left]=0;
                    return 0;//If the last 2 aren't compatible return 0
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        if(left & (1ll<<i)){//If the ith women is left
            if(compatibility[N-1][i]){//If the 2 are compatible
            currans+=solve(N-1,left - (1ll<<i));
            //Find the number of pairs after pairing them
            //and add all of them
            }
        }
    }
    currans%=p;//mod p
    ans[N-1][left]=currans;//memoise
    return ans[N-1][left];
}
ll solve(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<(1ll<<n);j++){
            ans[i][j]=-1;//memoisation initialisation
            //ans[i][j] represents i people left and
            //j is the bitmask for women left
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>compatibility[i][j];
        }
    }
    return solve(n,(1<<n)-1);//all men available, all women available because all bits set in mask
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cout<<solve()<<"\n";
}

Submission Info

Submission Time
Task O - Matching
User Everule
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1974 Byte
Status
Exec Time 500 ms
Memory 344320 KB

Test Cases

Set Name Score / Max Score Test Cases
All 100 / 100 0_00, 0_01, 0_02, 0_03, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12
Case Name Status Exec Time Memory
0_00 2 ms 4352 KB
0_01 2 ms 6400 KB
0_02 1 ms 256 KB
0_03 434 ms 344320 KB
1_00 1 ms 256 KB
1_01 1 ms 256 KB
1_02 86 ms 344320 KB
1_03 86 ms 344320 KB
1_04 106 ms 344320 KB
1_05 329 ms 344320 KB
1_06 361 ms 344320 KB
1_07 395 ms 344320 KB
1_08 469 ms 344320 KB
1_09 466 ms 344320 KB
1_10 500 ms 344320 KB
1_11 489 ms 344320 KB
1_12 494 ms 344320 KB