Submission #574713

#	Time	Username	Problem	Language	Result	Execution time	Memory
574713		KrisjanisP	Handcrafted Gift (IOI20_gift)	C++14	100 / 100	192 ms	28748 KiB

gift

#include "gift.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;

void compress(vector<ii>& one)
{
    sort(one.begin(),one.end());
    vector<ii> newOne;
    newOne.push_back(one[0]);
    for(ll i=1;i<one.size();i++)
    {
        if(one[i].first<=newOne.back().second)
            newOne.back().second=max(newOne.back().second,one[i].second);
        else
            newOne.push_back(one[i]);
    }
    one = newOne;
}

int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x) {
    vector<ii> one, two;
    for(ll i=0;i<r;i++)
    {
        if(x[i]==1) one.push_back({a[i],b[i]});
        else two.push_back({a[i],b[i]});
    }
    if(one.size())
        compress(one);
    vector<bool> same(n,false);
    for(ll i=0;i<one.size();i++)
    {
        for(ll j=one[i].first+1;j<=one[i].second;j++)
            same[j]=true;
    }
    vector<ll> vec(n,0);
    vec[0]=0;
    for(ll i=1;i<n;i++)
    {
        if(same[i]) vec[i]=vec[i-1];
        else vec[i]=1-vec[i-1];
    }
    vector<ll> ps(n,0);
    ps[0]=vec[0]; for(ll i=1;i<n;i++) ps[i]=ps[i-1]+vec[i];
    bool found = false;
    for(ll i=0;i<two.size();i++)
    {
        ll sum = ps[two[i].second];
        if(two[i].first) sum-=ps[two[i].first-1];
        if(sum==0||sum==(two[i].second-two[i].first+1))
        {
            found=true;
            break;
        }
    }
    if(found) return 0; // answer doesn't exist

    std::string res(n, 'R');
    for(ll i=0;i<n;i++)
        if(vec[i]) res[i]='B';
    
    craft(res);
    return 1;
}

Compilation message (stderr)

gift.cpp: In function 'void compress(std::vector<std::pair<long long int, long long int> >&)':
gift.cpp:12:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(ll i=1;i<one.size();i++)
      |                ~^~~~~~~~~~~
gift.cpp: In function 'int construct(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
gift.cpp:32:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(ll i=0;i<one.size();i++)
      |                ~^~~~~~~~~~~
gift.cpp:47:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(ll i=0;i<two.size();i++)
      |                ~^~~~~~~~~~~

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