Codeforces アンバランス / Unbalanced

Problem Statement

 

Given a string t, we will call it unbalanced if and only if the length of t is at least 2, and more than half of the letters in t are the same. For example, both voodoo and melee are unbalanced, while neither noon nor a is.

You are given a string s consisting of lowercase letters. Determine if there exists a (contiguous) substring of s that is unbalanced. If the answer is positive, show a position where such a substring occurs in s.

Constraints

 

• 2≦|s|≦10⁵
• s consists of lowercase letters.

Partial Score

 

• 200 points will be awarded for passing the test set satisfying 2≦N≦100.

Input

 

The input is given from Standard Input in the following format:

s

Output

 

If there exists no unbalanced substring of s, print -1 -1.

If there exists an unbalanced substring of s, let one such substring be s_as_a+1…s_b(1≦a<b≦|s|), and print a b. If there exists more than one such substring, any of them will be accepted.

Sample Input 1

 

needed

Sample Output 1

 

2 5

The string s₂s₃s₄s₅ = eede is unbalanced. There are also other unbalanced substrings. For example, the output 2 6 will also be accepted.

Sample Input 2

 

atcoder

Sample Output 2

 

-1 -1

The string atcoder contains no unbalanced substring.

说实话，水题一道，但没想出来还真就凉凉，开始用前缀和，毕竟才100*n*26，但是死活最后一个过不了，于是换了个方法。

一想最坏的情况就是隔一个一个相同，不然如果各两个就已经不可能是一半相同的了，于是只需要相隔一个相同或者相邻相同就直接可以输出了。

#include<iostream>
using namespace std;
int main()
{
	char arr[100000];
	scanf("%s",&arr);
	int n=strlen(arr);
	int p=0,a,b;
	for(int i=0;i<n-2;i++)
	{
		if(arr[i]==arr[i+1])
		{
			p=1;
			a=i;
			b=i+1;
			break;
		}
		else if(arr[i]==arr[i+2])
		{
			p=1;
			a=i;
			b=i+2;
			break;
		}
	}
	if(arr[n-2]==arr[n-1])
	{
		p=1;
		a=n-2;
		b=n-1;
	}
	if(p)
	{
		cout<<a+1<<' '<<b+1;
	}
	else
	{
		cout<<"-1 -1";
	}
}