Submission #443134

#	Time	Username	Problem	Language	Result	Execution time	Memory
443134		Abrar_Al_Samit	Nivelle (COCI20_nivelle)	C++17	110 / 110	153 ms	1228 KiB

nivelle

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;


#define debug(x) cerr << '[' << (#x) << "] = " << x << '\n';

template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update> ;

void PlayGround() {
    int N;
    cin >> N;
    string s; cin >> s;
    vector<vector<int>>app(26, vector<int>());
    for(int i=0; i<N; ++i) {
        int ch = s[i] - 'a';
        app[ch].push_back(i);
    }
    double colorfulness = 2;
    int l, r;
    for(int i=0; i<N; ++i) {
        vector<int>impIndices;
        for(int c=0; c<26; ++c) {
            auto it = lower_bound(app[c].begin(), app[c].end(), i);
            if(it==app[c].end()) continue;
            impIndices.push_back(*it);
        }
        
        sort(impIndices.begin(), impIndices.end());
        impIndices.erase(impIndices.begin());
        if(impIndices.empty()) continue;

        for(int j=0; j<impIndices.size(); ++j) {
            if(colorfulness > (double)(j+1) / (double)(impIndices[j]-i)) {
                colorfulness = (double)(j+1) / (double)(impIndices[j]-i);
                l = i, r = impIndices[j];
            }
        }
        if(colorfulness > ((double)(impIndices.size()+1)) / ((double)(N-i))) {
            colorfulness = ((double)(impIndices.size()+1) / ((double)(N-i)));
            l = i, r = N;
        }
        // debug(impIndices.size())
        // debug(colorfulness)
        // break;
    }
    if(colorfulness>1) l = 0, r = 1;
    cout << l+1 << ' ' << r << '\n';

    #ifndef ONLINE_JUDGE
        cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    #endif
} 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //#ifndef ONLINE_JUDGE
      //  freopen("input.txt", "r", stdin);
    //#endif
    PlayGround();

    return 0;
}

Compilation message (stderr)

nivelle.cpp: In function 'void PlayGround()':
nivelle.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int j=0; j<impIndices.size(); ++j) {
      |                      ~^~~~~~~~~~~~~~~~~~
nivelle.cpp:51:32: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |     cout << l+1 << ' ' << r << '\n';
      |                                ^~~~
nivelle.cpp:51:20: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |     cout << l+1 << ' ' << r << '\n';
      |                    ^~~

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