Submission #1289731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289731		mhaer	Norela (info1cup18_norela)	C++20	75 / 100	875 ms	580 KiB

norela

#include <bits/stdc++.h>
#define int long long
using namespace std;

int to_bits(vector<int>& numbers) {
    int number = 0;
    int cnt = 64;
    for (int i = numbers.size()-1;i >= 0;i--) {
        // cout << numbers[i] << " ";
        while (numbers[i] < cnt) {
            cnt--;
            number *= 2;
        }
        // cout << cnt << " " << number << " - ";
        number += 1;
    }
    while (--cnt) {
        number *= 2;
    }
    // cout << "\n";
    return number;
}

int target = 0;

vector<int> dp;
pair<int, vector<int>> bf(vector<int>& numbers, vector<int> fk, int index, int number) {
    if (index == numbers.size()) {
        if (number == target) {
            for (int i : fk) {
                dp[i] = min(dp[i], (int)fk.size());
            }
            return {0, fk};
        } else {
            return {[phone], fk};
        }
    }

    if (number == target) {
        return {0, fk};
    }
    // if (fk.size() >= dp[index]) {
    //     return {[phone], fk};
    // } else {
    //     dp[index]=fk.size();
    // }

    if (fk.size() >= dp[index]) {
        return {100000000000, fk};
    }

    fk.push_back(index);
    auto ans2 = bf(numbers, fk, index+1, number ^ numbers[index]);
    // cout << "1: " << (numbers[index]^number) << "\n";
    fk.pop_back();
    auto ans1 = bf(numbers, fk, index+1, number);   
    
    ans2.first += 1;
    auto result = min(ans1, ans2);
    return result;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n ,m;
    cin >> n >> m;
    vector<int> results(m);
    for (int i = 0;i < m;i++) {
        int l;
        cin >> l;
        vector<int> numbers(l);
        for (int& i : numbers) cin >> i;
        // for (int i : numbers) {
        //     cout << i << " ";
        // }
        // cout << "a\n";
        results[i] = to_bits(numbers);
    }

    for (int i = 1;i <= n;i++) {
        target *= 2;
        target += 1;
    }

    dp.resize(results.size(), 1000000000000);

    auto result = bf(results, {}, 0, 0);
    cout << result.first << "\n";
    for (int i : result.second) {
        cout << i+1 << " ";
    }
    cout << "\n";


}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 25 / 25
• Subtask 4: 0 / 25