Submission #340614

#	Time	Username	Problem	Language	Result	Execution time	Memory
340614		A_D	Nivelle (COCI20_nivelle)	C++14	0 / 110	1080 ms	21864 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=1e7;
string s;
int n,idx,lef,righ;
int mask;
du mn=1;
du dp[N];
int pre[112345][26];
du solve(int mask,int l,int r)
{
    vec.push_back(mask);
    du&ret=dp[mask];
    if(ret)return ret;
    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(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:92:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   92 | main()
      |      ^
nivelle.cpp: In function 'int main()':
nivelle.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         for(int i=0;i<vec.size();i++)dp[vec[i]]=0;
      |                     ~^~~~~~~~~~~

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