Submission #1193749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193749		chaeryeong	Handcrafted Gift (IOI20_gift)	C++20	100 / 100	229 ms	27812 KiB

gift

#include "gift.h"
#include <bits/stdc++.h>
using namespace std;
int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x) {
    vector <pair <int, int>> ee, ff;
    for (int i = 0; i < r; i++) {
        if (x[i] == 1) {
            ee.push_back({a[i], b[i]});
        } else {
            ff.push_back({a[i], b[i]});
        }
    }
    for (int i = 0; i < n; i++) {
        ee.push_back({i, i});
    }
    {
        sort(ee.begin(), ee.end());
        auto g = ee; ee.clear();
        for (auto i : g) {
            if (ee.empty() || ee.back().second < i.first) {
                ee.push_back(i);
            }
            ee.back().second = max(ee.back().second, i.second);
        }
    }
    string s;
    for (int i = 0; i < n; i++) {
        s += 'R';
    }
    int v = 0;
    for (int i = 1; i < (int)ee.size(); i++) {
        if (ee[i].first == ee[i - 1].second + 1) {
            v ^= 1;
        } else {
            for (int j = ee[i - 1].second + 1; j < ee[i].first; j++) {
                s[j] = (v == 1 ? 'R' : 'B');
            }
        }
        for (int j = ee[i].first; j <= ee[i].second; j++) {
            s[j] = (v == 0 ? 'R' : 'B');
        }
    }

    for (auto [x, y] : ff) {
        auto g = lower_bound(ee.begin(), ee.end(), pair <int, int> {x + 1, 0}) - ee.begin();
        if (g != 0) {
             g--;  
           if (ee[g].first <= x && y <= ee[g].second) {
                return 0;
            }
        }
    }
    craft(s); return 1;
}

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