oj.uz

Submission #217237

# Submission time Handle Problem Language Result Execution time Memory
217237 2020-03-29T09:42:21 Z Vimmer Zapina (COCI20_zapina) C++14
22 / 110
 1000 ms 384 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 52 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 52 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Execution timed out 1097 ms 384 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 52 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Execution timed out 1097 ms 384 KB Time limit exceeded
7 Halted 0 ms 0 KB -