#include <iostream>
using namespace std;
int rubabandiera(int n);
int main(){
//p e la posizione in cui il ragazzo si deve posizionare per vincere
int n,q,p;
cin>>q;
for(int i=0;i<q;i++){
cin>>n;
p=rubabandiera(n);
cout<<p<<"\n";
}
}
int rubabandiera(int n){
int i=0,c=0,p;
bool colpito=false;
int v[n];
for(int j=0;j<n;j++)v[j]=1;
while(c!=n-1){//continuo fin quando sono stati tutti colpiti tranne 1
if(i>=n)i=n-i;//controllo se lindice ha superato la dimensione del vettore
if(v[i]!=0){
p=i;
while(colpito==false){//continuo fin quando non trovo uno da colpire
if(++i>=n)i=n-i;
if(v[i]!=0){
v[i]=0;
colpito=true;
c++;
}
}
colpito=false;
}
i++;
}
return p+1;
}
In un secondo abbiamo un limite di complessità che si aggira sul miliardo di operazioni ovviamente questo in linea di massima , non considerando specifiche tecniche della macchina su cui stiamo sottoponendo il code; nel tuo caso peggiore , arrivi ad una complessità di 10^21 che rispetto al limite di 10^9 è un po troppo xd . pensa a come semplificare l eliminazione non più calcolandoti passo per passo se devi abbattere o no la persona, ma cercando di trovare una formula o una legge che riesca a semplificarti il calcolo della soluzione.
In realtà un lower bound è O(NQ)=10^{23} , in quanto hai Q=10^5 query dove in ognuna delle quali hai almeno N=10^{18} istruzioni: for(int j=0;j<n;j++)v[j]=1;
La complessità effettiva è in realtà più alta di O(NQ) in quanto quella simulazione non è lineare.
In ogni caso avendo così tante query devi trovare un modo veloce ( O(logN) o O(1) ) per svolgere una singola query. Il consiglio che posso darti per questo esercizio è controllare a mano i risultati per N= 1, 2, 3, ... e cercare un eventuale pattern.