Rotations

#include <stdio.h>
#include <iostream>
#include <memory.h>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

#define sqr(a) ((a) * (a))
#define pi 3.1415926535897932384626433832795

#define TASK "d"
//#define CONTEST 2

string s;

const long long A = 17, B = 972663749;

int hs(string st)
{
	int h = (int) st[0] - 'a';

	for(int i = 1; i < (int) st.length(); i++)
	{
		h = (h*A + st[i])%B;
	}

	return h;
}

bool cmp(string s1, string s2)
{
	if (s1.length() > s2.length())
		return true;
	
	if (s1.length() < s2.length())
		return false;

	int n = s1.length();
    int i = 0, j = n;
    int k = 0;

    int len = 0;
    while(i <= j)
    {
    	k = ceil((i+j)/2);
    	string sub1 = s1.substr(0, k);
    	string sub2 = s2.substr(0, k);
    	int h1 = hs(sub1);
    	int h2 = hs(sub2);

		if (h1 == h2)
		{
			if(sub1.compare(sub2) == 0)
			{
				len = k;
				i =	k + 1;
			}
			else
				j = k - 1;		
		}
		else
			j = k - 1;
    }

    if(len < n)
	{
		return s1[len] < s2[len];
	}
	else
		return false;

}

void Load()
{
	cin >> s;	
}

void Solve()
{
	string fs = s + s;

	string ms = s;
	int n = s.length();
	int fn = fs.length();
	
	for(int i = 1; i + n < fn; i++)
	{
		string sub_s = fs.substr(i, n);
		if(cmp(sub_s, ms))
			ms = sub_s;
	}

	cout << ms;	
}

int main()
{
#ifdef CONTEST
	freopen(TASK".in", "r", stdin);
	freopen(TASK".out", "w", stdout);
#endif
	
	Load();
	Solve();

	return 0;
}

Test 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: UNKNOWN

Test 9

Verdict: UNKNOWN

Test 10

Verdict: UNKNOWN

Test 11

Verdict: UNKNOWN

Test 12

Verdict: UNKNOWN