Submission #581663

#	Time	Username	Problem	Language	Result	Execution time	Memory
581663		AGE	Nivelle (COCI20_nivelle)	C++14	110 / 110	794 ms	21068 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;
int n,freq[N][26],vis[26];
double ans=1e18;

bool ok(int l,int mid){

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

    for(int j=0;j<26;j++){

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

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

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

    }

    return 1;

}
main()
{

    cin>>n;

    string s;
    cin>>s;
    int L,R;

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

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

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

        for(int j=0;j<26;j++)
            vis[j]=0;

        int lst=i,num=0;

        while(lst<n){

            vis[s[lst]-'a']=1;
            num++;

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

                int mid=(l+r+1)/2;

                if(ok(lst,mid))
                    l=mid;

                else r=mid-1;

            }

            lst+=l;

            double len=lst-i;
            double numm=num;

            if(numm/len<ans)
                ans=numm/len,L=i,R=lst-1;

        }
    }

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

    return 0;
}

Compilation message (stderr)

nivelle.cpp:34:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   34 | main()
      | ^~~~
nivelle.cpp: In function 'int main()':
nivelle.cpp:85:23: warning: 'R' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |     cout<<L+1<<" "<<R+1<<endl;
      |                       ^
nivelle.cpp:85:13: warning: 'L' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |     cout<<L+1<<" "<<R+1<<endl;
      |             ^

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