Submission #1281557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281557		aren_dance	Nivelle (COCI20_nivelle)	C++20	110 / 110	46 ms	836 KiB

nivelle

// oj us strah.cpp : This file contains the 'main' function. Program execution begins and ends there.
#define _CRT_SECURE_NO_WARNINGS
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <complex>
#include <cassert>
#include <cfloat>
#include <memory>
#include <chrono>
#include <random>
#include <climits>
#include <limits>
#include <bitset>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <tuple>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
#define ll long long 
using namespace std;
const int N = 1e5+1;
int n, m;
int pref[N][27];
int x[27];
pair<int,int> answ[27];
pair<int, int> max_p(pair<int,int> u,pair<int,int> v) {
	int sz1 = u.second - u.first + 1;
	int sz2 = v.second - v.first + 1;
	if (sz1 > sz2) {
		return u;
	}
	return v;
}
int main()
{
	cin >> n;
	string s;
	cin >> s;
	for (int i = 1;i <= 26;++i) {
		answ[i].second = -1;
	}
	for (int i = 1;i <= n;++i) {
		vector<int> p;
		x[s[i-1] - 'a'] = i;
		for (int j = 0;j < 26;++j) {
			if (x[j] == 0) {
				continue;
			}
			p.push_back(x[j]);
		}
		sort(p.rbegin(), p.rend());
		int c = 1;
		for (auto j : p) {
			if (j == i) {
				continue;
			}
			answ[c] = max_p(answ[c],make_pair(j+1,i));
			++c;    
		}
		answ[c] = max_p(answ[c], make_pair(1, i));
	}
	int val = 1;
	for (int i = 2;i <= 27;++i) {
		if (answ[i].first == 0) {
			continue;
		}
		if (answ[val].first == 0) {
			val = i;
			continue;
		}
		if ((val * (answ[i].second - answ[i].first + 1)) > i * (answ[val].second - answ[val].first + 1)) {
			val = i;                                
		}
	}
	cout << answ[val].first<<" "<<answ[val].second << '\n';
	return 0;
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file

Compilation message (stderr)

nivelle.cpp: In function 'int main()':
nivelle.cpp:73:29: warning: iteration 25 invokes undefined behavior [-Waggressive-loop-optimizations]
   73 |                 if (answ[i].first == 0) {
      |                     ~~~~~~~~^~~~~
nivelle.cpp:72:26: note: within this loop
   72 |         for (int i = 2;i <= 27;++i) {
      |                        ~~^~~~~

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