Submission #524608

#	Time	Username	Problem	Language	Result	Execution time	Memory
524608		lucri	Treasure (info1cup19_treasure)	C++17	100 / 100	16 ms	3052 KiB

treasure

#include <iostream>
using namespace std;
char c[200010];
int n,k,f[200010],urm[200010],ant[200010];
void rezolvare()
{
    for(int i=urm[0];i<=n;i=urm[i])
    {
        while(c[i]==c[urm[i]])
        {
            f[i]+=f[urm[i]];
            ant[urm[urm[i]]]=i;
            urm[i]=urm[urm[i]];
        }
        f[i]%=k;
        if(f[i]==0)
        {
            urm[ant[i]]=urm[i];
            ant[urm[i]]=ant[i];
            i=ant[ant[i]];
        }
    }
}
int main()
{
    cin>>n>>k;
    urm[0]=1;
    ant[n+1]=n;
    for(int i=1;i<=n;++i)
    {
        cin>>c[i];
        f[i]=1;
        ant[i]=i-1;
        urm[i]=i+1;
    }
    rezolvare();
    for(int i=urm[0];i<=n;i=urm[i])
        while(f[i]--)
            cout<<c[i];
    return 0;
}

• Subtask 1: 35 / 35
• Subtask 2: 65 / 65