Cod sursa(job #2407713)

Utilizator PaterucAPetruc Andrei Stefan PaterucA Data 17 aprilie 2019 10:23:18
Problema Cautare binara Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;

const int N=200010;

int n, k, lft;
bool usd[N];
vector<int> v(N, 0);

int main()
{
    cin>>n>>k;
    lft=n;
    string s(n,'*');
    for(int i=1; i<=n; i++)
    {
        int x;
        cin>>x;
        v[x]=i;
    }
    //sort(begin(v)+1,begin(v)+n+1);
    int cnt=n;
    int t=0;
    while(lft)
    {
        while(usd[v[cnt]])
            cnt--;
        s[v[cnt]-1]=t+'1';
        usd[v[cnt]]=true;
        lft--;
        for(int i=v[cnt]-1, j=k; j>0&&i>0; )
        {
            if(usd[i])
                {i-=2*k+1;continue;}
            usd[i]=true;
            j--;
            s[i-1]=t+'1';
            lft--;
            i--;
        }
        for(int i=v[cnt]+1, j=k; j>0&&i<=n; )
        {
            if(usd[i])
                {i+=2*k+1;continue;}
            usd[i]=true;
            j--;
            s[i-1]=t+'1';
            lft--;
            i++;
        }
        cnt--;
        t=t^1;
    }
    cout<<s;

    return 0;
}