Solução Informatica Intermediario - Semana 69

Solução por Samyra Almeida

Conhecimento prévio necessário:

Para resolver essa questão, basta fazermos uma busca binária na quantidade de cookies que podem ser feitos. Para cada interação da busca binária testamos se conseguimos fazer mid cookies, se sim, salvo mid como resposta atual, e tento aumentar a quantidade de cookies a serem feitas, caso contrário, diminuiremos a quantidade de cookies.

Para maior compreensão leia o código-solução abaixo:


// NOIC - Problemas da Semana 69 - Intermediário
// Solução por Samyra Almeida
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10, root = 340; // declaro maxn e root como constantes,
// observe que coloquei o root como 340 pq por alguma razao fica um pouquinho mais rapido quando n e no maximo 10^5
// nos testamos em alguns juizes e ficou mais rapido, mas se quiser usar como 320 fique a vontade.
int n, m;
int v[maxn], qtd[maxn], ultimo[maxn], prox[maxn]; // declaro as variaveis e vetores que irei precisar
void build()
{
for(int i = n ; i > 0 ; --i) // passo por todas as posiçoes do vetor, ou seja, por todos os buracos
{
int ini, fim;
ini = i/root;
fim = ini + 1;
ini *= root, fim *= root; // calculo a primeira e a ultima posicao do bloco que i pertence
// OBS: pode ficar um pouco confuso mas tente observar que na verdade a variavel fim guarda
// a primeira posicao do proximo bloco, ou seja, o bloco de i abrange as posiçoes de ini ate fim - 1.
for(int j = i ; j >= max(ini, 1) ; --j) // percorro da posiçao i ate o inicio do bloco de i
{
if(v[j] + j > n) // se o proximo pulo sai do vetor
{
qtd[j] = 1; // a quantidade de pulos para sair do vetor e 1
ultimo[j] = j; // a ultima posiçao que eu pulei dentro do meu bloco foi a posiçao j
}
else if(v[j] + j < fim) // se o proximo pulo e dentro o meu bloco, seria a mesma coisa de testar v[j] + j <= fim - 1
{
qtd[j] = qtd[j + v[j]] + 1; // a quantidade de pulos ate o final do bloco e igual a quantidade de pulos que o meu proximo cara deu ate o final do bloco mais 1 (meu pulo ate v[j] + j)
ultimo[j] = ultimo[j + v[j]]; // o ultimo de j e o mesmo que o de v[j] + j
}
else // se o meu proximo pulo for em alguma outra posiçao, ainda dentro do vetor mas fora do meu bloco
{
qtd[j] = 1; // a quantidade de pulos para sair do vetor e 1
ultimo[j] = j; // a ultima posiçao que eu pulei dentro do meu bloco foi a posiçao j
}
prox[j] = j + v[j]; // atualizo a posiçao do proximo pulo de j
}
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
for(int i = 1 ; i <= n ; ++i) cin >> v[i];
build(); // monto os vetores qtd, ultimo e prox.
for(int i = 0 ; i < m ; ++i) // processo todas as queries
{
int type, a;
cin >> type >> a;
if(type) // se for do tipo 1
{
int pulos = 0, x = a; // no inicio nao dei nenhum pulo e estou na posiçao a
while(true) // enquanto eu preciso pular de bloco
{
pulos += qtd[x]; // somo a pulos a quantidade de pulos para sair da posicao x ate a ultima posiçao que eu vou pular em meu bloco
x = ultimo[x]; // pulo ate a ultima posiçao que eu consigo em meu bloco
if(prox[x] > n) break; // se o proximo pulo for sair do vetor, paro o loop
x = prox[x]; // caso contrario, pulo para a proxima posicao
}
cout << x << " " << pulos << "\n"; // imprimo a resposta
}
else // se a query for do tipo 0
{
int b;
cin >> b;
v[a] = b; // atualizo a potencia do buraco a
int ini, fim;
ini = a/root;
fim = ini + 1;
ini *= root, fim *= root; // calculo a primeira e a ultima posicao do bloco que a pertence
// OBS: pode ficar um pouco confuso mas tente observar que na verdade a variavel fim guarda
//a primeira posicao do proximo bloco, ou seja, o bloco de a abrange as posiçoes de ini ate fim - 1.
for(int j = a ; j >= max(ini, 1) ; --j) // percorro o bloco da posiçao a ate o inicio do bloco
{
if(v[j] + j > n) // se o proximo pulo sai do vetor
{
qtd[j] = 1; // a quantidade de pulos para sair do vetor e 1
ultimo[j] = j; // a ultima posiçao que eu pulei dentro do meu bloco foi a posiçao j
}
else if(v[j] + j < fim) // se o proximo pulo e dentro o meu bloco, seria a mesma coisa de testar v[j] + j <= fim - 1
{
qtd[j] = qtd[j + v[j]] + 1; // a quantidade de pulos ate o final do bloco e igual a quantidade de pulos que o meu proximo cara deu ate o final do bloco mais 1 (meu pulo ate v[j] + j)
ultimo[j] = ultimo[j + v[j]]; // o ultimo de j e o mesmo que o de v[j] + j
}
else // se o meu proximo pulo for em alguma outra posiçao, ainda dentro do vetor mas fora do meu bloco
{
qtd[j] = 1; // a quantidade de pulos para sair do vetor e 1
ultimo[j] = j; // a ultima posiçao que eu pulei dentro do meu bloco foi a posiçao j
}
prox[j] = j + v[j]; // atualizo o proximo cara que eu irei pular.
}
}
}
}

view raw

noic-intermediario-s69.cpp

hosted with ❤ by GitHub