Submission #1094232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094232		0pt1mus23	Nivelle (COCI20_nivelle)	C++14	62 / 110	1052 ms	1624 KiB

nivelle

#include <bits/stdc++.h>
using namespace std;
#define needforspeed ios::sync_with_stdio(0);cin.tie(0);
#define int long long int
#define pb push_back
#define ins insert
#define endl '\n'
#define putr(x) cout<<x<<endl;return;
#define all(x) x.begin(),x.end()
#define _ << " " <<
const int mod = 1e9 +7,sze = 2e5 +23,inf = INT_MAX, L = 31; 

void opt1z(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    pair<int,int> ans={1,1};
    double ap = 1.0;
    if(n<=2e3){
        for(int i=0;i<n;i++){
            int st = 0;
            int frq = 0;

            for(int j=i;j<n;j++){
                if( ! ( st & (1<<(s[j]-'a')) )){
                    frq++;
                    st |= (1<<(s[j]-'a'));
                }
                // cout<<i<<" "<<j<<" "<<frq<<endl;
                if(ap > (frq + .0)/ (j-i +1)){
                    ap = (frq + .0)/ (j-i +1);
                    ans.first = i+1;
                    ans.second = j+1;
                }

            }
        }
    }
    else{

        set<char> dis;
        for(auto v:s){
            dis.ins(v);
        }
        vector<int> num(150);
        int c =0;
        for(auto v:dis){
            num[v]= (1<<c) ;
            c++;
        }
        int m=dis.size();
        for(int mask = 1;mask<(1<<m);mask++){
            int frq = __builtin_popcount(mask);
            vector<int> dp(n,inf);
            for(int i=0;i<n;i++){
                if(! ( mask & num[s[i]]) ){
                    continue;
                }
                if(!i){
                    dp[i]=i;
                }
                else{
                    dp[i]=dp[i-1];
                    dp[i]=min(dp[i],i);
                }
                if(dp[i]<=i){
                    double bp = (frq + .0)/ (i- dp[i] +1);
                    if(bp< ap){
                        ap = bp;
                        ans.first = dp[i]+1;
                        ans.second = i+1;
                    }
                }
                // cout<<mask<<" "<<i<<" "<<dp[i]<<endl;
            }
        }
    }

    cout<<ans.first<<" "<<ans.second<<endl;   
}
 
signed main() {
    needforspeed;
 
    int tt = 1;
    // cin>>tt;
    while(tt--){
        opt1z();
    }
 
    return 0;
}

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