| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 574707 | Valters07 | Handcrafted Gift (IOI20_gift) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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();
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 = mxr+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;
}