Submission #580971

#	Time	Username	Problem	Language	Result	Execution time	Memory
580971		AGE	Nivelle (COCI20_nivelle)	C++14	24 / 110	403 ms	5324 KiB

nivelle

#include<bits/stdc++.h>
#define F first
#define S second
#define int long long
#define pb push_back

using namespace std;
const int N=1e6,M=2e3,mod=1e9+7;
char x[6]={'a','b','c','d','e'};
vector<int>v;
int vis[10];
double anss=1e18;
int LL,RR;
int freq[N][6],n;
bool ok(int mid,int l){

    if(l+mid>=n)
        return 0;

    for(int i=0;i<5;i++){

        int x;
        if(l==0)
            x=freq[l+mid-1][i];

        else
            x=freq[l+mid-1][i]-freq[l-1][i];

        if(vis[i]==0&&x!=0)
            return 0;

    }

    return 1;

}
void bt(int index){

    if(index==5){

        for(int i=0;i<n;i++){

            int l=0,r=n;
            while(l<r){

                int mid=(l+r+1)/2;
                if(ok(mid,i))
                    l=mid;

                else r=mid-1;

            }

            double num=0;
            for(int i=0;i<5;i++)
                if(vis[i])
                    num++;

            double len=l;

            if(num/l<anss)
                anss=num/l,LL=i,RR=i+l-1;

        }

        return ;

    }

    vis[x[index]-'a']=1;
    bt(index+1);
    vis[x[index]-'a']=0;
    bt(index+1);

}

main()
{
    cin>>n;
    set<int>st;

    string s;
    cin>>s;
    if(n<=2000){

        double ans=1e18;
        int L,R;
        for(int i=0;i<n;i++){
            st.clear();
            for(int j=i;j<n;j++){

                st.insert(s[j]);
                double num=st.size();
                double len=(double)j-i+1;

                if(num/len<ans){

                    ans=num/len;
                    L=i,R=j;

                }

            }
        }
        cout<<L+1<<" "<<R+1<<endl;

    }

    else{

        for(int j=0;j<5;j++)
            freq[0][j]=(j==(s[0]-'a'));

        for(int i=1;i<n;i++)
            for(int j=0;j<5;j++)
                freq[i][j]=freq[i-1][j]+(j==(s[i]-'a'));

        bt(0);
        
        cout<<LL+1<<" "<<RR+1<<endl;
    }

    return 0;
}

Compilation message (stderr)

nivelle.cpp: In function 'void bt(long long int)':
nivelle.cpp:59:20: warning: unused variable 'len' [-Wunused-variable]
   59 |             double len=l;
      |                    ^~~
nivelle.cpp: At global scope:
nivelle.cpp:77:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   77 | main()
      | ^~~~
nivelle.cpp: In function 'int main()':
nivelle.cpp:105:27: warning: 'R' may be used uninitialized in this function [-Wmaybe-uninitialized]
  105 |         cout<<L+1<<" "<<R+1<<endl;
      |                           ^
nivelle.cpp:105:17: warning: 'L' may be used uninitialized in this function [-Wmaybe-uninitialized]
  105 |         cout<<L+1<<" "<<R+1<<endl;
      |                 ^

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