Submission #793324

#	Time	Username	Problem	Language	Result	Execution time	Memory
793324		SlavicG	Handcrafted Gift (IOI20_gift)	C++17	100 / 100	652 ms	46088 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) {
    std::string s(n, 'R');
    vector<int> p(n, 0);
    for(int i = 0; i < r; ++i) {
        if(x[i] == 1) {
            if(a[i] != b[i]) {
                p[a[i] + 1]++;
                if(b[i] + 1 < n) p[b[i] + 1]--;
            }
        }
    }
    for(int i = 0; i < n; ++i) {
        if(i) p[i] += p[i - 1];
        if(p[i]) s[i] = s[i - 1];
        else if(s[i - 1] == 'B') s[i] = 'R';
        else s[i] = 'B';
    }
    set<int> posR, posB;
    posR.insert(n);
    posB.insert(n);
    for(int i = 0; i < n; ++i) {
        if(s[i] == 'R') posR.insert(i);
        else posB.insert(i);
    }
    for(int i = 0; i < r; ++i) {
        auto A = *posR.lower_bound(a[i]);
        auto B = *posB.lower_bound(a[i]);
        int cnt = 0;
        if(A <= b[i]) ++cnt;
        if(B <= b[i]) ++cnt;
        if(cnt != x[i]) 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