Rubabandiere v2

Aiuto
1

Come posso migliorare?

#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;
}
2

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.

3

ps: per formattare il code puoi usare questi simboli ```

#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c;
  cin>>a>>b>>c;
  cout<<a+b+c<<"\n";
}
4

come hai fatto a calcolarti 10^21?

5

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.