Submission #300177

#	Time	Username	Problem	Language	Result	Execution time	Memory
300177		model_code	Handcrafted Gift (IOI20_gift)	C++17	100 / 100	272 ms	20068 KiB

gift

// limli-full
#include <bits/stdc++.h>

#include "gift.h"
using namespace std;

typedef pair<int, int> ii;

vector<ii> combine(vector<ii> ranges) {
    vector<ii> ans;
    if (ranges.empty()) return ranges;
    sort(ranges.begin(), ranges.end());
    int a = ranges[0].first, b = ranges[0].second;
    for (ii range : ranges) {
        if (range.first <= b) {
            b = max(b, range.second);
        } else {
            ans.push_back(ii(a, b));
            a = range.first;
            b = range.second;
        }
    }
    ans.push_back(ii(a, b));
    return ans;
}

int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
    vector<ii> ones, twos;
    for (int i = 0; i < r; i++) {
        ii range = ii(a[i], b[i]);
        if (x[i] == 1) {
            ones.push_back(range);
        } else {
            twos.push_back(range);
        }
    }
    ones = combine(ones);
    for (ii range : twos) {
        if (range.first == range.second) {
            return 0;
        }
        if (ones.empty()) continue;
        int bs = upper_bound(ones.begin(), ones.end(), ii(range.first, 1000000000)) - ones.begin() - 1;
        if (bs < 0) continue;
        if (ones[bs].first <= range.first && range.second <= ones[bs].second) {
            return 0;
        }
    }
    string ans(n, 'R');
    int pos = 0;
    for (int i = 1; i < n; i++) {
        if (!ones.empty() && ones[pos].first <= i - 1 && i <= ones[pos].second) {
            ans[i] = ans[i - 1];
        } else {
            ans[i] = 'R' + 'B' - ans[i - 1];
        }
        if (pos + 1 < (int)ones.size() && ones[pos].second <= i) {
            pos++;
        }
    }
    craft(ans);
    return 1;
}

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