Как мне избежать TLE в таких кодах?
Большинство моих кодов сталкиваются с похожими проблемами. Как мне это исправить?
Проблема здесь: http://usaco.org/index.php?page=viewproblem2&CPID = 692
#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;
string rotate_s(string s){
int m= s.size();
string s2;
for(int i=0; i<m; i++){
s2[i] = s[(i+m-1)%m];
}
return s+s2;
}
int main()
{
string s;
int n;
cin>>s>>n;
int k = s.size();
while(k<n){
s = rotate_s(s);
k = s.size();
}
cout<<s[n-1]<<endl;
return 0;
}
Решение
Вам не нужно строить строку, просто исправляя индекс постепенно:
char foo(const std::string& s, std::size_t index)
{
auto size = s.size();
// What would be the size of the (smaller) string containing index
while (size <= index) {
size *= 2;
}
while (size != s.size()) {
size /= 2;
if (index >= size) { // index is on the second part
index = (index - 1) % size; // negate the rotate
}
}
return s[index];
}
Так
0 1 2 3 4 5 | 6 7 8 9 10 11
0 1 2 3 4 5 | 5 0 1 2 3 4
0 1 2 | 3 4 5
0 1 2 | 2 0 1
0 1 2
Другие решения
Других решений пока нет …