oj.uz

Submission #198440

# Submission time Handle Problem Language Result Execution time Memory
198440 2020-01-26T03:38:15 Z model_code April Fools (LMIO17_faktai) C++17
100 / 100
 228 ms 376 KB 
/**
 * Uždavinio "Balandžio pirma" sprendimas.
 *
 * Perrinksime visas galimas faktų aibes, kurių iš viso yra 2^20 ~= 1000000.
 * Parinkę kiekvieną aibę, patikrinsime šias sąlygas:
 *
 * - Kiekvienas faktas yra paskelbtas bent vieno dienraščio.
 * - Kiekvienas dienraštis yra paskelbęs lygiai vieną neteisingą faktą.
 *
 * Šis sprendimas naudoja bitų aritmetiką aibių operacijoms.
 */

#include <iostream>
#include <vector>
#include <set>

using namespace std;

const int MAX_N = 1000;
const int MAX_F = 6;

// Globalūs uždavinio kintamieji:
// - kiekvieno dienraščio paskelbti faktai, bei
// - visi paskelbti faktai.

vector<int> faktai(MAX_N);
int visi_faktai;

int bituSkaicius(int a) {
    int skaicius = 0;
    while (a > 0) {
        skaicius += (a & 1);
        a >>= 1;
    }
    return skaicius;
}

void patikrink(int parinkti_faktai,
               int N,
               int* min_faktu,
               int* max_faktu) {
    // Kiekvienas faktas yra paskelbtas bent vieno dienraščio:
    if ((parinkti_faktai & visi_faktai) != parinkti_faktai) {
        return;
    }
    // Kiekvienas dienraštis yra paskelbęs lygiai vieną neteisingą faktą.
    for (int i = 0; i < N; i++) {
        if (bituSkaicius(parinkti_faktai & faktai[i]) != 1) {
            return;
        }
    }
    // Rinkinys yra teisingas, atnaujiname parinktą atsakymą.
    int kiek_faktu = bituSkaicius(parinkti_faktai);
    if (*min_faktu > kiek_faktu) *min_faktu = kiek_faktu;
    if (*max_faktu < kiek_faktu) *max_faktu = kiek_faktu;
}

void perrink(int parinkti_faktai,
             int i,
             int N,
             int F,
             int* min_faktu,
             int* max_faktu) {
    if (i > F) {
        patikrink(parinkti_faktai, N, min_faktu, max_faktu);
    } else {
        parinkti_faktai ^= 1 << i;
        perrink(parinkti_faktai, i + 1, N, F, min_faktu, max_faktu);
        parinkti_faktai ^= 1 << i;
        perrink(parinkti_faktai, i + 1, N, F, min_faktu, max_faktu);
    }
}

int main() {
    int N; cin >> N;
    int F; cin >> F;
    for (int i = 0; i < N; i++) {
        int k; cin >> k;
        for (int j = 0; j < k; j++) {
            int f; cin >> f;
            faktai[i] |= 1 << f;
            visi_faktai |= 1 << f;
        }
    }

    int min_faktu = N + 1, max_faktu = 0;
    perrink(0, 1, N, F, &min_faktu, &max_faktu);

    cout << min_faktu << " " << max_faktu << endl;
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 27 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 26 ms 256 KB Output is correct
5 Correct 31 ms 256 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 256 KB Output is correct
2 Correct 20 ms 256 KB Output is correct
3 Correct 20 ms 256 KB Output is correct
4 Correct 228 ms 256 KB Output is correct
5 Correct 24 ms 256 KB Output is correct
6 Correct 29 ms 256 KB Output is correct
7 Correct 32 ms 256 KB Output is correct
8 Correct 5 ms 248 KB Output is correct
9 Correct 27 ms 256 KB Output is correct
10 Correct 5 ms 256 KB Output is correct
11 Correct 26 ms 256 KB Output is correct
12 Correct 31 ms 256 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 5 ms 256 KB Output is correct
15 Correct 5 ms 256 KB Output is correct
16 Correct 5 ms 256 KB Output is correct
17 Correct 5 ms 256 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct