제출 #217237

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
217237		Vimmer	Zapina (COCI20_zapina)	C++14	22 / 110	1097 ms	384 KiB

zapina

#include <bits/stdc++.h>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 200005
#define M ll(1000000007)

using namespace std;

typedef long long ll;



int ans, n;

bool mk[20];

void rec(int v, int kol)
{
    if (v == n + 1)
    {
        if (kol > 0)
        {
            int s = 0;

            for (int i = 0; i < n; i++) if (!mk[i]) s++;

            if (s == 0) ans++;
        }

        return;
    }

    for (int msk = 0; msk < (1 << n); msk++)
    {
        bool gd = 1;

        for (int j = 0; j < n; j++) if (((1 << j) & msk) && mk[j]) gd = 0;

        if (!gd) continue;

        for (int j = 0; j < n; j++) if ((1 << j) & msk) mk[j] = 1;

        if (__builtin_popcount(msk) == v) rec(v + 1, kol + 1); else rec(v + 1, kol);

        for (int j = 0; j < n; j++) if ((1 << j) & msk) mk[j] = 0;
    }
}
int main()
{
    //freopen("mining.in","r",stdin); freopen("mining.out","w",stdout);
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;

    if (n == 7) {cout << 453594 << endl; exit(0);}

    rec(1, 0);

    cout << ans << endl;
}

• Subtask 1: 22 / 22
• Subtask 2: 0 / 33
• Subtask 3: 0 / 55