Submission #339956

#	Time	Username	Problem	Language	Result	Execution time	Memory
339956		Hazem	Nivelle (COCI20_nivelle)	C++14	110 / 110	245 ms	12540 KiB

nivelle

/*
ID: tmhazem1
LANG: C++14
TASK: pprime
*/

#include <bits/stdc++.h>
using namespace std;

#define S second
#define F first
#define LL long long
const int N = 2e5 + 10;


LL LINF = 100000000000000000;
LL INF = 1000000000;

int n,freq[N][30];
string s;
vector<int>idx;

int get_first(int i,int c){

    int l = i+1,r = n+1;
    while(l<r){
        int mid = (l+r)/2;
        if(freq[mid][c]-freq[i][c])r = mid;
        else l = mid+1;
    }
    return l;
}

int main()
{
    //freopen("out.txt","w",stdout);
    scanf("%d",&n);
    cin>>s;s = '*'+s;

    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);
    
    double ans = INF;
    int l,r;

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

        for(int j=0;j<=27;j++)
            if(j==s[i]-'a')continue;
            else 
            idx.push_back(get_first(i,j));

        sort(idx.begin(),idx.end());
        for(int j=0;j<idx.size();j++)
            if(ans>(j+1.0)/(idx[j]-i))ans = (j+1.0)/(idx[j]-i),l = i,r = idx[j]-1;         
        
        idx.clear();
    }

    printf("%d %d\n",l,r);

}       

Compilation message (stderr)

nivelle.cpp: In function 'int main()':
nivelle.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(int j=0;j<idx.size();j++)
      |                     ~^~~~~~~~~~~
nivelle.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~

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