Submission #209322

#	Time	Username	Problem	Language	Result	Execution time	Memory
209322		papa	Nivelle (COCI20_nivelle)	C++14	110 / 110	41 ms	764 KiB

nivelle

#include <bits/stdc++.h>

using namespace std;

//ideja je da pomocu two-pointer tehnike
//izracunamo za svako slovo najduzi podstring koji
//nam treba iz uslova zadatka i onda samo uporedimo tih 26
//vrednosti

typedef long long ll;

const int maxn = 1e5;
int n;
string s;
double ans;
double bans;
int lr,rr;
int lr2,rr2;

void input()
{
    cin >> n;
    cin >> s;
}

void output()
{
    cout << lr+1 << " " << rr+1;
}

void brute()
{
    bans = 3000000.0;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            int cnt[26];
            for(int k=0;k<26;k++) cnt[k]=0;
            for(int k=i;k<=j;k++) cnt[s[k]-'a']++;
            int cn = 0;
            for(int k=0;k<26;k++)
                if(cnt[k]) cn++;
            if((double)cn/(j-i+1) < bans)
            {
                bans = (double)cn/(j-i+1);
                lr2 = i;
                rr2 = j;
            }
        }
    }
}

int randd(int a,int b)
{
    return a+rand()%(b-a+1);
}

void testprimer()
{
    n = 100;
    s= "";
    for(int i=0;i<n;i++) s+="a";
    for(int i=0;i<n;i++)
    {
        int ro = randd(0,25);
        s[i] = (char)(ro+'a');
    }
}

bool uporedi()
{
   return ans==bans;
}

void razlika()
{
    cout << n << "\n" << s << "\n";
    cout << "Resi" << "\n";
    cout << ans << "\n";
    cout << "Brute" << "\n";
    cout << bans << "\n";
    exit(0);
}


void resii()
{
    ans = 300000.0;
    for(int k=1;k<=26;k++)
    {
        //cout << k << "\n";
        int cnt[26];
        for(int i=0;i<26;i++) cnt[i] = 0;
        int cn = 0;
        //int ii;
        int le = 0;
        int ri = 0;

        for(int i=0;i<s.size();i++)
        {
            cnt[s[i]-'a']++;
            if(cnt[s[i]-'a']==1) cn++;
            if(cn==k){ri=i; break;}
        }

        if(cn < k) break;

        //cout << le << " " << ri << "\n";
        if((double)k/(ri-le+1) < ans)
        {
               ans = (double)k/(ri-le+1);
               lr = le;
               rr = ri;
        }
        //maks = max(maks,ri-le+1);

        for(ri = ri+1;ri<s.size();ri++)
        {
            cnt[s[ri]-'a']++;
            if(cnt[s[ri]-'a']==1) cn++;
            while(cn > k)
            {
                cnt[s[le]-'a']--;
                if(cnt[s[le]-'a']==0) cn--;
                le++;
            }

            //cout << le << " " << ri << "\n";

            if((double)k/(ri-le+1) < ans)
            {
               ans = (double)k/(ri-le+1);
               lr = le;
               rr = ri;
            }
        }
    }
}


void testiraj()
{
    int brprim = 1009;
    for(int i=1;i<=brprim;i++)
    {
        testprimer();
        brute();
        resii();
        if(!uporedi())
        {
            razlika();
        }
        else
        {
            cout << "OK" << "\n";
        }
    }
}


void r()
{
    input();
    resii();
    output();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cerr.tie(0);

    bool tt = 0;

    if(tt) testiraj();
    else r();

    return 0;
}

Compilation message (stderr)

nivelle.cpp: In function 'void resii()':
nivelle.cpp:100:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<s.size();i++)
                     ~^~~~~~~~~
nivelle.cpp:118:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(ri = ri+1;ri<s.size();ri++)
                       ~~^~~~~~~~~

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