Submission #844609

#	Time	Username	Problem	Language	Result	Execution time	Memory
844609		vjudge1	Nivelle (COCI20_nivelle)	C++17	72 / 110	26 ms	676 KiB

nivelle

#pragma GCC optimize("unroll-loops,Ofast,O3")
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define spc << " " <<
#define all(x) x.begin(), x.end()
#define ll long long
#define int long long
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define st first
#define nd second
#define inf 1000000009
#define MOD 1000000007

using namespace std;




void solve(){
    int n; cin >> n;
    string tem; cin >> tem;
    string s="0"+tem;
    double mini = (double) 1;
    ii ans={1,1};

    set<char> check;
    for(int i=1; i<=n; i++) check.insert(s[i]);

    for(int dif=2; dif<=check.size(); dif++){
        //cerr << dif << endl;
        int ptr1=1, ptr2=1;
        int nums[26]; memset(nums, 0, sizeof(nums));
        nums[s[1]-'a']++;
        int curcol=1;

        while(ptr2<=n && ptr1<=ptr2){
            //cerr << ptr1 spc ptr2 spc curcol spc dif << endl;
            int flag=0;
            while(ptr2<=n &&(curcol<dif || (ptr2<n && curcol==dif && nums[s[ptr2+1]-'a']>0))){
                ptr2++;
                if(nums[s[ptr2]-'a']++==0) curcol++;
            }
            if(ptr2>n) break;
            
            double newy = ((double) curcol) / ((double) (ptr2-ptr1+1));
            //cerr << "oh" spc newy << endl;
            if(newy < mini){
                mini = newy;
                ans.st=ptr1;
                ans.nd=ptr2;
            }
            while(curcol>=dif){
                if(nums[s[ptr1]-'a']--==1) curcol--;
                ptr1++;
            }
        }
    }
    cout << ans.st spc ans.nd << endl;
}



signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out","w",stdout);
    #endif
    

    ll t=1;
    //cin >> t;
    while(t--) solve();
}

Compilation message (stderr)

nivelle.cpp: In function 'void solve()':
nivelle.cpp:33:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::set<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int dif=2; dif<=check.size(); dif++){
      |                    ~~~^~~~~~~~~~~~~~
nivelle.cpp:42:17: warning: unused variable 'flag' [-Wunused-variable]
   42 |             int flag=0;
      |                 ^~~~

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