Submission #198440

#	Time	Username	Problem	Language	Result	Execution time	Memory
198440		model_code	April Fools (LMIO17_faktai)	C++17	100 / 100	228 ms	376 KiB

faktai

/**
 * 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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 60 / 60