Rotations

input/code.cpp: In function 'int main()':
input/code.cpp:40:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(s.length()-vec[i]<rl) i++;
                           ^

#include <bits/stdc++.h>

using namespace std;

vector<int> suffix_array(string& str) {
  if(str.length()==0)
    return vector<int>();

  vector<int> cur;
  for(auto c : str) cur.push_back(c);
  int n = cur.size();
  for(int length=1;;length*=2) {
    vector<pair<pair<int,int>,int>> pairs(n); // pair, original, position index
    for(int i=0;i<n;i++) {
      pair<int,int> new_pair = {cur[i], i+length<n?cur[i+length]:-1};
      pairs[i] = {new_pair, i};
    }
    sort(pairs.begin(), pairs.end());
    int code = 0;
    for(int i=0;i<n;i++) {
      if(i!=0&&pairs[i].first!=pairs[i-1].first) 
        code++;
      cur[pairs[i].second]=code;
    }
    if(code==n-1) {
      vector<int> result(n);
      for(int i=0;i<n;i++)
        result[i] = pairs[i].second;
      return result;
    }
  }
}

int main() {
  string s;
  cin >> s;
  int rl = s.length(), i=0;
  s += s;
  auto vec = suffix_array(s);
  while(s.length()-vec[i]<rl) i++;
  cout << s.substr(vec[i], rl) << endl;
  return 0;
}

Test 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

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