Submission #574708

#	Time	Username	Problem	Language	Result	Execution time	Memory
574708		Valters07	Handcrafted Gift (IOI20_gift)	C++14	100 / 100	200 ms	28408 KiB

gift

#include <bits/stdc++.h>
#include "gift.h"
#pragma GCC optimize("O2,unroll-loops")
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define en cin.close();return 0;
#define pb push_back
#define fi first//printf("%lli\n",cur);
#define se second//scanf("%lli",&n);
#define r0 return 0;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x)
{
    vector<pair<int,int> > eq;
    for(int i = 0;i<r;i++)
        if(x[i]==1)
            eq.pb({a[i],b[i]});
    sort(eq.begin(),eq.end());
    vector<pair<int,int> > seg;
    if(!eq.empty())
    {
        int mxl = eq[0].fi, mxr = eq[0].se;
        for(int i = 1;i<eq.size();i++)
        {
            if(mxr<eq[i].fi)
            {
                seg.pb({mxl,mxr});
                mxl=eq[i].fi;
            }
            mxr=max(mxr,eq[i].se);
        }
        seg.pb({mxl,mxr});
    }
    else
        seg.pb({0,0});
    int segsiz = seg.size(), fin = seg.back().se;
    for(int i = 0;i<seg[0].fi;i++)
        seg.pb({i,i});
    for(int i = 1;i<segsiz;i++)
    {
        for(int j = seg[i-1].se+1;j<seg[i].fi;j++)
            seg.pb({j,j});
    }
    for(int i = fin+1;i<n;i++)
        seg.pb({i,i});
    sort(seg.begin(),seg.end());
    string ans = "";
    for(int i = 0;i<seg.size();i++)
    {
        int len = seg[i].se-seg[i].fi+1;
        char ch = (i%2?'R':'B');
        while(len--)
            ans+=ch;
    }
    assert(ans.size()==n);
    int pf[n+1];
    pf[0]=0;
    for(int i = 1;i<=n;i++)
        pf[i]=pf[i-1]+(ans[i-1]=='R');
    bool ok = 1;
    for(int i = 0;i<r;i++)
    {
        if(x[i]==2)
        {
            int l = a[i], r = b[i], c = pf[r+1]-pf[l], len = r-l+1;
            ok&=(c!=len&&c!=0);
        }
    }
    if(!ok)
        return 0;
    craft(ans);
    return 1;
}

Compilation message (stderr)

gift.cpp: In function 'int construct(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
gift.cpp:24:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for(int i = 1;i<eq.size();i++)
      |                       ~^~~~~~~~~~
gift.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i = 0;i<seg.size();i++)
      |                   ~^~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from gift.cpp:1:
gift.cpp:56:22: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |     assert(ans.size()==n);
      |            ~~~~~~~~~~^~~

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