Submission #434863

#	Time	Username	Problem	Language	Result	Execution time	Memory
434863		kevinxiehk	Handcrafted Gift (IOI20_gift)	C++17	100 / 100	234 ms	27628 KiB

gift

#include "gift.h"
#include "bits/stdc++.h"
#define pb emplace_back
using namespace std;
struct req{
    int l, r;
};
bool cmp(req a, req b) {return a.l < b.l;}
int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
    vector<req> one, two;
    for(int i = 0; i < r; i++) {
        req tmp;
        tmp.l = a[i];
        tmp.r = b[i];
        if(x[i] == 1) one.pb(tmp);
        else two.pb(tmp);
    }  
    sort(one.begin(), one.end(), cmp);
    bool arr[n + 5];
    arr[0] = 0;
    int rt = 0, pt = 0;
    for(int i = 0; i < n; i++) {
        if(i > 0) {
            if(i <= rt) arr[i] = arr[i - 1];
            else arr[i] = arr[i - 1] ^ 1;
        }
        while(pt < int(one.size()) && one[pt].l == i) {
            rt = max(rt, one[pt].r);
            pt++;
        }
    }
    int ms[n + 5];
    ms[0] = -1;
    for(int i = 1; i < n; i++) {
        if(arr[i] ^ arr[i - 1]) ms[i] = i - 1;
        else ms[i] = ms[i - 1];
    }
    for(auto x: two) {
        if(x.l > ms[x.r]) return 0;
    }
    string ans = "";
    for(int i = 0; i < n; i++) ans += (arr[i] ? "R" : "B");
    craft(ans);
    return 1;
}

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