Submission #580975

#	Time	Username	Problem	Language	Result	Execution time	Memory
580975		AGE	Nivelle (COCI20_nivelle)	C++14	38 / 110	578 ms	5228 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-1>=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;


        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()
      | ^~~~

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