#include <iostream>
#include <vector>
using namespace std;
void riprogramma(int N, int K, vector<int> &C) {
int Seq = 1;
if(K > 2) {
for(int i = 1; i < N; i++) {
if(Seq == 3) {
Seq = 1;
for(int j = 1; j <= K; j++) {
if(j != C[i-3] && j != C[i-1]) {
C[i-2] = j;
break;
}
}
}
if(C[i] == C[i-1]) Seq++;
else if(Seq == 2) {
for(int j = 1; j <= K; j++) {
if(i == 2) {
if(j != C[i-1]) {
C[i-2] = j;
Seq = 1;
break;
}
} else {
if(j != C[i-1] && j != C[i-3]) {
C[i-2] = j;
Seq = 1;
break;
}
}
}
}
}
} else {
for(int i = 1; i < N; i++) {
if(Seq == 3) {
Seq = 1;
for(int j = 1; j <= K; j++) {
if(j != C[i-3] && j != C[i-1]) {
C[i-2] = j;
break;
}
}
}
if(C[i] == C[i-1]) Seq++;
else if(Seq == 2) {
if(i <= N/2+1) {
C[i-2] = C[i-1] == 1 ? 2 : 1;
for(int j = i-3; j >= 0; j--) {
if(C[j] == C[j+1]) C[j] = C[j+1] == 1 ? 2 : 1;
else break;
}
} else {
C[i-1] = C[i-2] == 1 ? 2 : 1;
for(int j = i; j < N; j++) {
if(C[j] == C[j-1]) C[j] = C[j-1] == 1 ? 2 : 1;
else break;
}
}
Seq = 1;
}
}
}
if(Seq == 2) {
for(int i = 1; i <= K; i++) {
if(i != C[N-2]) {
C[N-1] = i;
break;
}
}
} else if(Seq == 3) {
for(int i = 1; i <= K; i++) {
if(i != C[N-1] && i != C[N-3]) {
C[N-2] = i;
break;
}
}
}
}
Stavo provando a risolvere mascherine sporche e tutto procede bene tranne che per 3 casi dell’ultimo subtask il quale mi va in TLE e nell’ultimo testcase del subtask 4 il quale mi dice che la disposizione non è quella ottimale. Sostanzialmente quello che vado a fare è vedere in quale caso mi trovo e comportarmi di conseguenza. Seq serve per salvarsi la lunghezza in cui appaiono 2 o più mascherine uguali quindi nella sequenza 1 1 1 2 1 Seq sarà uguale a 3. Credo che il problema sia nel caso in cui K sia uguale a 2 ovvero non sapendo di per certo quale strategia ottimale adottare, nel caso in cui Seq sia uguale a 2 cambio o il primo o il secondo elemento della coppia in base a se i si trova o nella prima o nella seconda metà della sequenza (in modo, nel peggiore dei casi, di cambiar il minimo numero di mascherine). Tuttavia c’è anche un problema di ottimizzazione del codice che mi va in TLE che al 99% sono sicuro che accada perché scorro nuovamente la sequenza per cambiare i valori nel caso in cui K sia uguale a 2, però non mi viene in mente niente per poter ovviare a questo problema.