Submission #546409

#	Time	Username	Problem	Language	Result	Execution time	Memory
546409		Nguyennams1	Nivelle (COCI20_nivelle)	C++14	110 / 110	439 ms	724 KiB

nivelle

/*=====================================================================================
                Nothing is impossible, only you think it is impossible                 
                        Try, try, try again until you succeed     
                           Pratice, practice, and practice
I hated every minute of training, but I said, ‘Don’t quit. Suffer now and live the rest of your life as a champion.' - Mohamed Ali 
=====================================================================================*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n; 
string s; 
pair<ll, ll> kq;
double ans=1000000000;

void xuli(ll x)
{
    map<char, ll> mp;
    ll sl=0;
    ll l=1;
    for (ll r=1; r<=n; r++)
    {       
        if (mp[s[r]]==0) ++sl;
        ++mp[s[r]];
        while (l<r && sl>x)
        {
            --mp[s[l]];
            if (mp[s[l]]==0) --sl;
            ++l;
        }
        if ((sl*1.0)/(r-l+1)<ans)
        {
            ans=(sl*1.0)/(r-l+1);
            kq.first=l;
            kq.second=r;
        }//  cout<<l<<" "<<r<<" "<<sl<<endl;
        // for (auto it: mp) cout<<it.first<<" "<<it.second<<endl; cout<<endl;
    }
}

void solve()
{
    cin>>n;
    cin>>s;
    s="@"+s+"$";
    ll cnt=0, l=1;
    kq.first=1; kq.second=1;
    for (ll i=1; i<=n; i++) 
    {
        if (s[i]==s[i+1]) ++cnt; 
        else 
        {
            if (1.0/(cnt+1)<ans)
            {
                ans=1.0/(cnt+1);   //   cout<<cnt<<endl;
                kq.first=l;
                kq.second=i;
            }
            l=i+1;
            cnt=0;
        }
    }
    for (ll i=1; i<=100; i++) xuli(i);
    cout<<kq.first<<" "<<kq.second;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
   
    solve();
    return 0;
}

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