Submission #430032

#	Time	Username	Problem	Language	Result	Execution time	Memory
430032		schse	Handcrafted Gift (IOI20_gift)	C++17	100 / 100	334 ms	29944 KiB

gift

#include "gift.h"
#include <bits/stdc++.h>
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif

struct requirement
{
    int a, b, x;
    bool operator<(const requirement &other)
    {
        return a != other.a ? a < other.a : b < other.b;
    }
};

int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x)
{
    set<pair<int, int>> s;

    vector<requirement> re;
    for (int i = 0; i < a.size(); i++)
        re.push_back({a[i], b[i], x[i]});
    sort(re.rbegin(), re.rend());
    for (auto i : re) //update single color
    {
        if (i.x == 1)
        {
            auto it = s.lower_bound(make_pair(i.a, i.b));
            while (it != s.end())
            {
                if (it->first > i.b)
                    break;
                i.b = max(i.b, it->second);
                s.erase(it);
                it = s.lower_bound({i.a, i.b});
            }
            s.insert({i.a, i.b});
            s = s;
        }
    }
    vector<int> prefarr;
    for (int v = 0, i = 0; i < n; i++)
    {
        while (s.size() && s.begin()->second < i)
            s.erase(s.begin());
        if (!s.size() || s.begin()->first >= i)
            v++;
        prefarr.push_back(v);
    }

    for (auto i : re) //update single color
    {
        if (i.x == 2)
        {
            if (prefarr[i.a] == prefarr[i.b])
                return 0;
        }
    }

    std::string sr(n, 'R');
    for (int i = 0; i < n; i++)
    {
        sr[i] = prefarr[i] % 2 ? 'R' : 'B';
    }
    craft(sr);
    return 1;
}

Compilation message (stderr)

gift.cpp: In function 'int construct(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
gift.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~

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