oj.uz

Submission #849736

# Submission time Handle Problem Language Result Execution time Memory
849736 2023-09-15T08:50:42 Z efedmrlr Nivelle (COCI20_nivelle) C++17
110 / 110
 26 ms 752 KB 
#include <bits/stdc++.h>
#define int long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int (i) = 0; (i) < (n); (i)++)



using namespace std;

const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 1e6+5;
int n,m,q;
void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

}
string s;
int cnt[26];
int num = 0;
vector<int> ans(27);
vector<array<int,2> > ansr(27);
void solve() {
    cin>>n;
    cin>>s;
    for(int i = 0; i<26; i++) cnt[i] = 0;
    for(int k = 1; k<=26; k++) {
        int i = 0, j = 0;
        int num = 0;
        for(int i = 0; i<26; i++) cnt[i] = 0;
        while(j < n) {
            //cout<<"j:"<<j<<"\n";

            cnt[s[j] - 'a']++;
            assert(i <= j);

            if(cnt[s[j] - 'a'] == 1) {
                num++;
            }
            while(num > k) {
                //cout<<"i:"<<i<<"\n";    
                cnt[s[i] - 'a']--;
                if(cnt[s[i] - 'a'] == 0) {
                    num--;
                }
                i++;
                
            }
            assert(num <= k);

            if(j - i + 1 > ans[k]) {
                ans[k] = j - i + 1;
                ansr[k] = {i,j};
            }
            j++;
        } 
    }
    
    long double res2 = INF;
    int l,r;
    for(int i = 1; i<=26; i++) {
        long double res = (long double) i / ans[i];

        if(res2 > res) {
            

            l = ansr[i][0];
            r = ansr[i][1];
            res2 = res;
        }
    }
    cout<<l+1<<" "<<r+1<<"\n";

}
 
signed main() {
    
    //fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

Compilation message

nivelle.cpp: In function 'void solve()':
nivelle.cpp:74:23: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |     cout<<l+1<<" "<<r+1<<"\n";
      |                       ^
nivelle.cpp:74:13: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |     cout<<l+1<<" "<<r+1<<"\n";
      |             ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 600 KB Output is correct
2 Correct 8 ms 584 KB Output is correct
3 Correct 8 ms 600 KB Output is correct
4 Correct 9 ms 600 KB Output is correct
5 Correct 8 ms 600 KB Output is correct
6 Correct 8 ms 600 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 600 KB Output is correct
2 Correct 9 ms 600 KB Output is correct
3 Correct 9 ms 604 KB Output is correct
4 Correct 9 ms 752 KB Output is correct
5 Correct 10 ms 600 KB Output is correct
6 Correct 13 ms 752 KB Output is correct

Subtask #5
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 600 KB Output is correct
2 Correct 25 ms 600 KB Output is correct
3 Correct 23 ms 600 KB Output is correct
4 Correct 23 ms 600 KB Output is correct
5 Correct 24 ms 600 KB Output is correct
6 Correct 26 ms 600 KB Output is correct