oj.uz

Submission #887686

# Submission time Handle Problem Language Result Execution time Memory
887686 2023-12-15T02:51:00 Z chanhchuong123 Nivelle (COCI20_nivelle) C++14
110 / 110
 25 ms 656 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

const int MAXN = 1e5 + 4;
int n;
double ans = 2e9;
pair<int, int> pos;
char a[MAXN];

main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	#ifdef ngchuong
		freopen("C.inp", "r", stdin);
		freopen("C.out", "w", stdout);
	#endif

	cin >> n >> (a + 1);
	for (int k = 1; k <= 26; k++) {
        int sum = 0; vector<int> cnt(26, 0);
        for (int l = 1, r = 1; r <= n; r++) {
            cnt[a[r] - 'a']++;
            if (cnt[a[r] - 'a'] == 1) sum++;
            while (sum > k) {
                if (cnt[a[l] - 'a'] == 1) sum--;
                cnt[a[l] - 'a']--; l++;
            }
            if (sum == k && ans > double(k) / (r - l + 1)) {
                ans = double(k) / (r - l + 1); pos = {l, r};
            }
        }
	}
	cout << pos.fi << ' ' << pos.se;
}

Compilation message

nivelle.cpp:15:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   15 | main() {
      | ^~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 604 KB Output is correct
2 Correct 7 ms 476 KB Output is correct
3 Correct 7 ms 604 KB Output is correct
4 Correct 7 ms 604 KB Output is correct
5 Correct 7 ms 604 KB Output is correct
6 Correct 6 ms 604 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 656 KB Output is correct
2 Correct 7 ms 604 KB Output is correct
3 Correct 7 ms 604 KB Output is correct
4 Correct 8 ms 644 KB Output is correct
5 Correct 7 ms 600 KB Output is correct
6 Correct 8 ms 604 KB Output is correct

Subtask #5
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 600 KB Output is correct
2 Correct 22 ms 604 KB Output is correct
3 Correct 21 ms 604 KB Output is correct
4 Correct 21 ms 604 KB Output is correct
5 Correct 23 ms 628 KB Output is correct
6 Correct 25 ms 600 KB Output is correct