이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
using ll = long long;
const int maxn = 1e6 + 5;
struct dat {
int l,r,cnt;
dat() {
l=1;
r=1;
cnt=1e9;
}
bool operator<(const dat& o) const {
int len = r-l+1;
int ocnt = o.cnt;
int olen = o.r-o.l+1;
// cnt/len < ocnt/olen
return cnt*olen < ocnt*len;
}
void print() {
cout<<l+1<<" "<<r+1<<endl;
}
};
int n;
vector<int> pos[26];
string s;
int a[maxn];
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n;
cin>>s;
for (int i=0; i<n; i++) {
a[i] = int(s[i]-'a');
pos[a[i]].push_back(i);
}
dat ans;
for (int i=0; i<n; i++) {
dat cur;
cur.l = i;
cur.r = i;
cur.cnt = 1;
if (cur < ans) {
ans = cur;
}
vector<int> w;
for (int c=0; c<26; c++) {
if (c==s[i]) continue;
auto iter = upper_bound(pos[c].begin(), pos[c].end(), i);
if (iter == pos[c].end()) continue;
w.push_back(*iter);
}
sort(w.begin(), w.end());
for (int idx: w) {
cur.r = idx-1;
if (cur < ans) {
ans = cur;
}
cur.cnt++;
}
cur.r = n-1;
if (cur < ans) {
ans = cur;
}
}
ans.print();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |