Well, in today’s contest i tried to solve the string problem, but my code failed bcs it exceded the time limit. Can someone tell me how i can make the code execute faster?
This is my code btw.
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
#include <string>
using namespace std;
bool isprefix(string a, string b){
if(a.size() >= b.size()) return false;
for(int i = 0; i < a.size(); i++){
if(a[i] != b[i]){
return false;
}
}
return true;
}
int main()
{
int cases; cin>> cases;
while(cases > 0){
vector <string> entrada;
int entradas; cin>>entradas;
cin.get();
while (entradas > 0){
string str;
getline(cin,str);
entrada.push_back(str);
entradas--;
}
vector <int> numbers;
for(int i = 0; i < entrada.size(); i++){
bool pref = false;
for(int j = 0; j < entrada.size(); j++){
if(i != j){
if(isprefix(entrada[i],entrada[j])){
pref = true;
break;
}
}
}
if(!pref) numbers.push_back(i);
}
int q; cin>>q;
cin.get();
while(q > 0){
string str;
getline(cin,str);
if(str[0] == '1'){
int a = str[2]-'0';
int i;
for(i = 3; str[i]>= 48 && str[i]<= 57; i++){
a = 10*a + (str[i]-'0');
}
entrada.push_back(entrada[a-1]+str[i+1]);
for(int i = 0; i < numbers.size(); i++){
if(isprefix(entrada[numbers[i]],entrada[entrada.size()-1])){
numbers.erase(numbers.begin()+i);
}
}
bool pref = false;
for(int i = 0; i < entrada.size(); i++){
if(isprefix(entrada[entrada.size()-1],entrada[i])){
pref = true;
break;
}
}
if(!pref) numbers.push_back(entrada.size()-1);
}
else if(str[0] == '2'){
string aux = entrada[numbers[0]];
for(int i = 0; i < numbers.size()-1; i++){
aux = min(aux, entrada[numbers[i+1]]);
}
int r;
for(r = 0; r < entrada.size(); r++){
if(entrada[r] == aux){
break;
}
}
cout<<r+1<<endl;
}
else{
string aux = entrada[numbers[0]];
for(int i = 0; i < numbers.size()-1; i++){
aux = max(aux, entrada[numbers[i+1]]);
}
int r;
for(r = 0; r < entrada.size(); r++){
if(entrada[r] == aux){
break;
}
}
cout<<r+1<<endl;;
}
q--;
}
cases--;
}
}