Submission #319696

#	Time	Username	Problem	Language	Result	Execution time	Memory
319696		northlake	Handcrafted Gift (IOI20_gift)	C++17	20 / 100	1596 ms	476460 KiB

gift

#include<gift.h>
#include<bits/stdc++.h>

using namespace std;

int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
    // clean up requirements
    vector<tuple<int,int,int>> remaining_requirements {};
    for (int i = 0; i < r; i++) {
        if ((a[i] == b[i]) && x[i] == 2) {
            return 0;
        } else if (a[i] == b[i]) continue;
        else {
            remaining_requirements.push_back({a[i], b[i], x[i]});
        }
    }

    // build all possibilities
    vector<string> possibilities = {""};
    for (int i = 0; i < n; i++) {
        vector<string> new_possibilities = {};
        for (string el : possibilities) {
            new_possibilities.push_back(el + 'B');
            new_possibilities.push_back(el + 'R');
        }
        possibilities = new_possibilities;
    }

    //check if possibility meets requirements
    for (string s : possibilities) {
        bool possible = true;
        for (auto r : remaining_requirements) {
            int beginning, ending, value;
            tie(beginning, ending, value) = r;
            if (value == 1) {
                for (int i = beginning; i <= ending; i++) {
                    if (s[beginning] != s[i]) {
                        possible = false;
                        break;
                    }
                }
            } else {
                bool two_colors = false;
                for (int i = beginning; i <= ending; i++) {
                    if (s[beginning] != s[i]) {
                        two_colors = true;
                        break;
                    }
                }
                if (!two_colors) {
                    possible = false;
                    break;
                }
            }
            if (!possible) break;
        }
        if (possible) {
            craft(s);
            return 1;
        }
    }
    return 0;
}

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