Submission #973976

#	Time	Username	Problem	Language	Result	Execution time	Memory
973976		Amirreza_Fakhri	Nivelle (COCI20_nivelle)	C++17	110 / 110	41 ms	652 KiB

nivelle

// In the name of the God
#include <bits/stdc++.h>
#define ll long long
// #define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pii pair <int, int>
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")

const int inf = 1e9+7;
const int mod = 998244353;
const int maxn = 1e5+5;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, p[26];
string s;
vector <int> v;

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> s;
    double ans = inf;
    int l, r;
    memset(p, -1, sizeof p);
    for (int i = 0; i < n; i++) {
        p[s[i]-'a'] = i;
        v.clear();
        for (int j = 0; j < 26; j++) {
            if (p[j] != -1) v.pb(p[j]);
        }
        v.pb(-1);
        sort(all(v));
        for (int j = 0; j < v.size()-1; j++) {
            double res = (1.0*(v.size()-1-j))/(i-v[j]);
            // cout << res << '\n';
            if (res < ans) {
                ans = res;
                l = v[j]+1, r = i;
            }
        }
    }
    cout << l+1 << ' ' << r+1 << '\n';
    return 0;
}







/*
srand(time(0));
cout << (rand()%1900) + 1 << ' ' << (rand()%2)+5 << '\n';
*/

Compilation message (stderr)

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

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