Submission #344479

#	Time	Username	Problem	Language	Result	Execution time	Memory
344479		limabeans	Nivelle (COCI20_nivelle)	C++17	110 / 110	175 ms	1916 KiB

nivelle

#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==a[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;
}

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