Submission #527378

#	Time	Username	Problem	Language	Result	Execution time	Memory
527378		stefantaga	Handcrafted Gift (IOI20_gift)	C++14	100 / 100	163 ms	24604 KiB

gift

#include <bits/stdc++.h>
#include "gift.h"
#include <vector>
#include <cassert>
#include <cstdio>
#include <string>
using namespace std;
int smen[500005];
int ok[500005];
int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x) {
    int i;
    for (i=0;i<r;i++)
    {
        a[i]++;b[i]++;
        if (a[i]==b[i]&&x[i]==2)
        {
            return 0;
        }
    }
    for (i=0;i<=n;i++)
    {
        smen[i]=ok[i]=0;
    }
    for (i=0;i<r;i++)
    {
        if (x[i]==1)
        {
            smen[a[i]]++;
            smen[b[i]+1]--;
        }
    }
    for (i=1;i<=n;i++)
    {
        smen[i]=smen[i]+smen[i-1];
        if (smen[i]!=0)
        {
            ok[i]=ok[i-1]+1;
        }
    }
    for (i=0;i<r;i++)
    {
        if (x[i]==1)
        {
            continue;
        }
        if (ok[b[i]]-ok[a[i]-1]==b[i]-a[i]+1)
        {
            return 0;
        }
    }
    string s;
    s.resize(n);
    s[0]='R';
    for (i=1;i<n;i++)
    {
        if (ok[i+1]<=1)
        {
            if (s[i-1]=='R')
            {
                s[i]='B';
            }
            else
            {
                s[i]='R';
            }
        }
        else
        {
            s[i]=s[i-1];
        }
    }
    craft(s);
    return 1;
}
#ifdef HOME
static int n, r;
static std::vector<int> a, b, x;
static std::string s;
static int possible = 0;
static int called = 0;
void craft(std::string &_s)
{
    assert(!called);
    s = _s;
    assert((int) s.size() == n);
    for (int i = 0; i < n; i++) {
        assert(s[i] == 'R' || s[i] == 'B');
    }
    called = 1;
}

int main()
{
    assert(scanf("%d %d", &n, &r) == 2);
    a.resize(r);
    b.resize(r);
    x.resize(r);
    for (int i = 0; i < r; i++) {
        assert(scanf("%d %d %d", &a[i], &b[i], &x[i]) == 3);
    }

    fclose(stdin);

    possible = construct(n, r, a, b, x);

    assert(possible == 0 || possible == 1);

    printf("%d\n", possible);

    if (possible == 1) {
        printf("%s\n", s.c_str());
    } else {
        assert(!called);
    }

}
#endif // HOME

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