Submission #433311

#	Time	Username	Problem	Language	Result	Execution time	Memory
433311		Tiago_Marques	Handcrafted Gift (IOI20_gift)	C++17	100 / 100	261 ms	27152 KiB

gift

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

using namespace std;

typedef long long int ll;
typedef pair<int, int> ii;

#define REP(i, a, b) for (ll i=a; i<b; i++)
#define fs first
#define sd second
#define pb push_back
#define mp make_pair

int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x)
{
    vector<ii> same;
    vector<ii> different;
    string ans;
    REP(i, 0, r)
    {
        if (x[i] == 1)
            same.pb (mp(a[i], b[i]));
        else
            different.pb (mp(a[i], b[i]));
    }
    sort (same.begin(), same.end());
    sort (different.begin(), different.end());
    int iterador = 1;
    ans += "R";
    for (auto u: same)
    {
        if (u.fs < iterador)
        {
            while (iterador <= u.sd)
            {
                ans += ans.back();
                iterador ++;
            }
        }
        else
        {
            while (iterador <= u.fs)
            {
                if (ans.back() == 'R')
                    ans += 'B';
                else
                    ans += 'R';
                iterador ++;
            }
            while (iterador <= u.sd)
            {
                ans += ans.back();
                iterador ++;
            }
        }
    }
    while (iterador < n)
    {
        if (ans.back() == 'R')
            ans += 'B';
        else
            ans += 'R';
        iterador ++;
    }
    int ultimo[n] = {};
    int last_R = -1, last_B = -1;
    REP(i, 0, n)
    {
        if (ans[i] == 'R')
        {
            ultimo[i] = last_B;
            last_R = i;
        }
        else
        {
            ultimo[i] = last_R;
            last_B = i;
        }
    }
    for (auto u: different)
    {
        if (ultimo[u.sd] < u.fs)
            return 0;
    }
    craft(ans);
    return 1;
}

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