Submission #793252

#	Time	Username	Problem	Language	Result	Execution time	Memory
793252		ln_e	Handcrafted Gift (IOI20_gift)	C++17	35 / 100	111 ms	21100 KiB

gift

#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho
#include "gift.h"
using ll=long long;
using ld=long double;
int const INF=1000000005;
ll const LINF=1000000000000000005;
ll const mod=6700417;
ld const PI=3.14159265359;
ll const MAX_N=3e5+5;
ld const EPS=0.00000001;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define endl '\n'
#define sz(a) (int)a.size()
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll pref[500005],cnt[500005];
int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x) {
 string ans="";   
for(ll i=0;i<n;i++)
{
    ans+='.';
}
for(ll i=0;i<r;i++){
   if(x[i]==1){
    pref[a[i]]++;
    pref[b[i]+1]--;
   }
}
for(ll i=0;i<n;i++){
    if(i-1>=0){
        pref[i]+=pref[i-1];
    }
    if(i-1>=0){
        cnt[i]+=cnt[i-1];
    }
    if(pref[i]>=1){
        ans[i]='R';
        cnt[i]++;
    }else {
        ans[i]='B';
    }
}
for(ll i=0;i<r;i++)
{
    if(x[i]==2){
        ll st=0;
        if(a[i]-1>=0){
            st=cnt[a[i]-1];
        }
        ll val=cnt[b[i]]-st;
        if(val==b[i]-a[i]+1){
            return 0;
        }
        if(val==0){
            ans[a[i]]='R';
            if(val+1==b[i]-a[i]+1){
                return 0;
            }
        }

    }
}
craft(ans);
return 1;
}

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