Submission #340621

#	Time	Username	Problem	Language	Result	Execution time	Memory
340621		A_D	Nivelle (COCI20_nivelle)	C++14	62 / 110	1101 ms	155752 KiB

nivelle

/*
ID: antwand1
TASK: barn1
LANG: C++
*/
#include <bits/stdc++.h>
#define ll long long
#define du long double
#define F first
#define S second
using namespace std;
vector<int> vec;
const int N=67108880;
string s;
int n,idx,lef,righ;
int mask;
du mn=1;
du dp[N];
int pre[112345][26];
bool ok(int&l,int&r,int&mask)
{
    for(int i=0;i<26;i++){
        int q=pre[r][i]-pre[l-1][i];
        if(q){
            q=(1<<i)&mask;
            if(q==0)return 0;
        }
    }
    return 1;
}
int bs(int mask,int le)
{
    int l=le,r=n,ret=le-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(ok(le,mid,mask)){
            ret=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    return ret;
}
int bs2(int mask,int le)
{
    int r=le,l=1,ret=le+1;
    while(l<=r){
        int mid=(l+r)/2;
        if(ok(mid,le,mask)){
            ret=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    return ret;
}
du solve(int mask,int l,int r)
{
    vec.push_back(mask);
    du&ret=dp[mask];
    if(ret)return ret;
    r=bs(mask,r)+1;
    l=bs2(mask,l)-1;
    du f=0;
    for(int i=0;i<26;i++){
        int q=pre[r-1][i]-pre[l][i];
        if(q)f++;
        ret+=q;
    }
    ret=f/ret;
    if(l!=0){
        int ad=s[l]-'a';
        ad=(1<<ad);
        ret=min(ret,solve(mask|ad,l,r));
    }
    if(r!=n+1){
        int ad=s[r]-'a';
        ad=(1<<ad);
        ret=min(ret,solve(mask|ad,l,r));
    }
    return ret;
}
void get(int mask,int l,int r)
{
    du&ret=dp[mask];
    if(ret)return;
    while(r<=n){
        int q=s[r]-'a';
        if((1<<q)&mask)r++;
        else break;
    }
    while(l>=1){
        int q=s[l]-'a';
        if((1<<q)&mask)l--;
        else break;
    }
    du f=0;
    for(int i=0;i<26;i++){
        int q=pre[r-1][i]-pre[l][i];
        if(q)f++;
        ret+=q;
    }
    ret=f/ret;
    if(ret<mn){
        mn=ret;
        lef=l+1;
        righ=r-1;
    }
    if(l!=0){
        int ad=s[l]-'a';
        ad=(1<<ad);
        get(mask|ad,l,r);
    }
    if(r!=n+1){
        int ad=s[r]-'a';
        ad=(1<<ad);
        get(mask|ad,l,r);
    }
    return;
}
main()
{
    //freopen("barn1.in","r",stdin);freopen("barn1.out","w",stdout);
    cin>>n;
    cin>>s;
    s="#"+s;
    for(int i=1;i<=n;i++){
        for(int j=0;j<26;j++){
            pre[i][j]=pre[i-1][j]+(s[i]-'a'==j);
        }
    }
    for(int i=1;i<=n;i++){
        mask=1<<(s[i]-'a');
        du u=solve(mask,i,i);
        if(u<mn){
            mn=u;
            idx=i;
        }
        for(int i=0;i<vec.size();i++)dp[vec[i]]=0;
        vec.clear();
    }
    mask=1<<(s[idx]-'a');
    mn=2;
    get(mask,idx,idx);
    cout<<lef<<" "<<righ<<endl;
}

Compilation message (stderr)

nivelle.cpp:121:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  121 | main()
      |      ^
nivelle.cpp: In function 'int main()':
nivelle.cpp:139:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |         for(int i=0;i<vec.size();i++)dp[vec[i]]=0;
      |                     ~^~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 17 / 17
• Subtask 3: 13 / 13
• Subtask 4: 25 / 25
• Subtask 5: 0 / 48