Witam.
Mam problem z podlinkowanym zadaniem - Smakołyki .
Od kilku dni usiłuję go zrobić na różne sposoby, ale za każdym razem wysyłając program do sprawdzenie na testach dostaję komunikat o błędnych odpowiedziach. Co najgorsze moje rozwiązania działają na małych ciągach, ale na takich liczących już kilkadziesiąt tysięcy już nie więc trudno mi sprawdzić co powoduje niewłaściwe działanie programu.
#include <iostream>
using namespace std;
long long triangular_number(int n);
int main(){
int n,m;
cin>>n>>m;
int tab[n];
for(int i=0; i<n; ++i){
cin>>tab[i];
}
if(m==1) cout<<n;
else{
int i=0;
int j=1;
while(i+1<n && tab[i]==tab[i+1]){
++i;
}
j=i+1;
int kind[m+1];
fill(kind,kind+m+1,1);
--kind[tab[i]];
--kind[tab[j]];
bool p=false;
int oldj=0;
long long s=n;
while(j+1<n && i<n){
while(j+1<n && kind[tab[j+1]]){
++j;
kind[tab[j]]=0;
}
if(p)
s+=j-i+(j>oldj ? triangular_number(j-oldj) : 0);
else
s+=triangular_number(j-i+1);
if(j+1<n){
if(tab[j]==tab[j+1]){
++j;
i=j;
for(int p=0; p<i; ++p)
kind[tab[p]]=1;
kind[tab[j]]=0;
p=false;
}
else{
while(i<n && !kind[tab[j+1]]){
kind[tab[i]]=1;
++i;
}
kind[tab[i]]=0;
}
if(i>=j){
j=i;
p=false;
}
else{
p=true;
oldj=j+1;
}
}
}
cout<<s;
}
return 0;
}
long long triangular_number(int n){
return (static_cast<long long>(n)*(n-1))/2;
}
Wyżej jedno z moich rozwiązań - funkcja triangular_number()
wylicza liczbę możliwości w zależności od długości podciągu nie zliczając jednocześnie podciągów jednoelementowych - są to tak zwane liczby trójkątne, stąd więc nazwa. W tabeli kind[]
przechowywane są liczby aktualnie rozpatrywanego ciągu 0 oznacza że liczba już wystąpiła więc kolejne wystąpienie kończy ciąg, a 1 odwrotnie.
Pewną trudnością jest cofanie się, ponieważ gdy na przykład w ciągu 1 2 3 4 5 1 6 7 8 zaczniemy od liczby 1 i skończymy na 5, to potem musimy rozpatrzyć także ciąg zaczynający się od 2 i kończący na 8 jednocześnie uważając żeby nie zliczyć drugi raz możliwości od 2 do 5.
Nie do końca wiem jak rozwiązać to w prostszy sposób unikając tego zamieszania z cofaniem i odejmowaniem. Zresztą zamieszczony kod nie działa w odpowiedni sposób - dla większych ciągów odpowiedzi są nieprawidłowe.
Proszę o pomoc.