Submission #319700

#	Time	Username	Problem	Language	Result	Execution time	Memory
319700		northlake	Handcrafted Gift (IOI20_gift)	C++17	20 / 100	1620 ms	493408 KiB

gift

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

using namespace std;

bool one_color(string s) {
    for (int i = 0; i < s.size(); i++) {
        if (s[0] != s[i]) {
            return false;
        }
    }
    return true;
}

bool two_color(string s) {
    for (int i = 0; i < s.size(); i++) {
        if (s[0] != s[i]) {
            return true;
        }
    }
    return false;
}

bool check(string s, vector<pair<int,int>> requirements[]) {
    int i = s.size()-1;
    for (auto r : requirements[i]) {
        int beginning = r.first; int value = r.second;
        if (value == 1) {
            if (!one_color(s.substr(beginning, i-beginning+1))) return false;
        }
        else {
            if (!two_color(s.substr(beginning, i-beginning+1))) return false;
        }
    }
    return true;
}

int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
    // clean up requirements
    vector<pair<int,int>> requirement_ending_at_i[n] {};
    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 {
            requirement_ending_at_i[b[i]].push_back({a[i], x[i]});
        }
    }

    // build all possibilities and check if still meets requirements
    vector<string> possibilities = {""};
    for (int i = 0; i < n; i++) {
        vector<string> new_possibilities = {};
        for (string el : possibilities) {
            if (check((el + 'B'), requirement_ending_at_i)) new_possibilities.push_back(el + 'B');
            if (check((el + 'R'), requirement_ending_at_i)) new_possibilities.push_back(el + 'R');
        }
        possibilities = new_possibilities;
    }

    // build result
    if (possibilities.size() > 0) {
        craft(possibilities[0]);
        return 1;
    } else {
        return 0;
    }
}

Compilation message (stderr)

gift.cpp: In function 'bool one_color(std::string)':
gift.cpp:7:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~
gift.cpp: In function 'bool two_color(std::string)':
gift.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~

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