Submission #918907

#	Time	Username	Problem	Language	Result	Execution time	Memory
918907		phamducminh	Nivelle (COCI20_nivelle)	C++17	0 / 110	161 ms	644 KiB

nivelle

//******************/
//*   I<3   C++    */
//*  I WANT ANY AC */
//* I LOVE PROGRAM!*/
//*IT'S long longERESTING*/
//* I LOVE PROGRAM!*/
//*  IN CONTESTS   */
//*   GET SCORE    */
//*    AC CODE     */
//*     LET'S      */
//*      GO        */
//*  Written by:   */
//*   Duc Minh     */






#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <deque>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

using namespace std;
// using namespace __gnu_pbds;

#define  file(name)  freopen(name".inp", "r", stdin);\
                     freopen(name".out", "w", stdout);
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define TIME        (1.0 * clock() / CLOCKS_PER_SEC)
#define all(a)      a.begin(),a.end()
#define endl        "\n"
#define all1(a)     a+1,a+n+1
#define unordered_map  map
// #define push_back   emplace_back
// #define gcd(a,b)    __gcd(a,b);
// #define lcm(a,b)    (a*b)/gcd(a,b);

const long long INF = (long long)1e18;
const long long MOD = (long long)1e9+7;
const long long MODD = 1e9; /// 998244353
const long long maxN = 25009;






///--------------------------------


void solve();

signed main(){

    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);


    // file("tbrackets");







    long long t;


    // cin >> t;

    t=1;



    while (t--){




        solve();


    }





    cerr << "Time elapsed: " << TIME << "s.\n";
    cerr << "ducminh" << "\n";
    return 0;
}



///--------------------[PROBLEM SOLUTION]--------------------///


int n;
string s;

void sub1(){

    long long li=0,lj=0,mm[26];
    long double ans=INF;
    for (int i=1; i<=n; i++){
        for (int j=i+1; j<=n; j++){
            int d=0;
            fill(mm,mm+26,0);
            for (int pos=i; pos<=j; pos++){
                mm[s[pos-1]-'a']++;
                if (mm[s[pos-1]-'a']==1) d++;
                // cout << mm[s[pos-1]-'a'] << "\n";
            }

            // cout << d << ' ' << i << ' ' << j << "\n";

            if (1.0*d/(j-i+1)<ans){

                ans=1.0*d/(j-i+1);
                li=i; lj=j;
            }
        }
    }

    // cout << ans << "\n";
    cout << li << ' ' << lj << "\n";

    exit(0);
}


void sub5(){

    long long li=0,lj=0,mm[26];
    long double ans=INF;
    unordered_map<int,int> mp;

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

        int l=1, r=1;

        while (r<=n){
            mp[s[r-1]-'a']++;

            while (mp[s[l-1]-'a']>i){

                mp[s[l-1]-'a']--;

                if (mp[s[l-1]-'a']==0){
                    mp.erase(s[l-1]-'a');
                }
                l++;
            }

            if (mp.size()==i){

                long double tam=1.0*mp.size()/(r-l+1);

                if (tam<ans ) ans=tam,li=l,lj=r;
            }

            r++;
        }
    }

    // cout << ans << "\n";
    cout << li << ' ' << lj << "\n";
}

void solve(){

    
    
    

    cin >> n >> s;

    
    // if (n<=100) sub1();
    

    sub5();
}

Compilation message (stderr)

nivelle.cpp: In function 'void sub5()':
nivelle.cpp:170:26: warning: comparison of integer expressions of different signedness: 'std::map<int, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  170 |             if (mp.size()==i){
      |                 ~~~~~~~~~^~~
nivelle.cpp:149:25: warning: unused variable 'mm' [-Wunused-variable]
  149 |     long long li=0,lj=0,mm[26];
      |                         ^~

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