Submission #623970

#	Time	Username	Problem	Language	Result	Execution time	Memory
623970		jophyyjh	Handcrafted Gift (IOI20_gift)	C++14	100 / 100	259 ms	29180 KiB

gift

/**
 * For x[i] = 1, the whole range should be the same. Therefore, after considering all
 * x[i]=1 we would've obtained a series of subranges, each of which should be
 * monochromatic. It suffices to color the subranges one by one in alternating color.
 * 
 * Time Complexity: O(n + r)
 * Implementation 1
*/

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

typedef std::vector<int>    vec;


int construct(int n, int r, vec a, vec b, vec x) {
    vec x1_a, x1_b;
    for (int i = 0; i < r; i++) {
        if (x[i] == 1) {
            x1_a.push_back(a[i]);
            x1_b.push_back(b[i]);
        }
    }
    std::sort(x1_a.begin(), x1_a.end());
    std::sort(x1_b.begin(), x1_b.end());
    int m = x1_a.size();
    vec parent(n, -1);
    for (int pos = 0, i = 0, j = 0, current = -1, layer = 0; pos < n; pos++) {
        while (j < m && x1_b[j] < pos)
            j++, layer--;
        if (layer > 0)
            parent[pos] = current;
        else
            current = -1;
        while (i < m && x1_a[i] <= pos)
            i++, layer++;
        if (layer > 0)
            current = pos;
    }

    std::string color;
    for (int pos = 0, c = 0; pos < n; pos++) {
        if (parent[pos] == -1) {
            color.push_back(c == 0 ? 'R' : 'B');
            c ^= 1;
        } else {
            color.push_back(color[parent[pos]]);
        }
    }
    vec red_count(n + 1);
    red_count[0] = 0;
    for (int i = 0; i < n; i++)
        red_count[i + 1] = red_count[i] + (color[i] == 'R');
    bool possible = true;
    for (int i = 0; i < r && possible; i++) {
        int reds = red_count[b[i] + 1] - red_count[a[i]];
        int blues = b[i] - a[i] + 1 - reds;
        assert(reds >= 0 && blues >= 0);
        if (x[i] == 1)
            possible &= (reds == 0 || blues == 0);
        else
            possible &= (reds > 0 && blues > 0);
    }
    if (possible)
        craft(color);
    return possible;
}

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