Cod sursa(job #2310469)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 31 decembrie 2018 17:59:50
Problema Farfurii Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <bits/stdc++.h>
#define MAX 5000000000
using namespace std;
ifstream f("farfurii.in");
ofstream g("farfurii.out");
long long N,K,st=1,dr,mij,minim,ans,rest;
int number,V[100006],l;

int main()
{
    f>>N>>K;
    dr=N;
    minim=MAX;
    while(st<dr)
    {
        mij=(st+dr)/2;
        long long nr=((mij-1)*mij)/2;
        if(labs(nr-K)<minim)
        {
            ans=mij;
            minim=labs(nr-K);
        }
        if(nr<K) st=mij+1;
        else
        if(nr>K)
        dr=mij;
        else
        if(nr==K) break;
    }
    rest=K-(((ans-1)*ans)/2);
    if(rest) number=1;
    for(l=1;l<=N-ans-number;l++) V[l]=l;

    if(rest)
    {
        V[l]=V[l-1]+1+rest;
        V[N]=V[l-1]+1;
        for(int i=N-1;i>l;i--)
        {
            if(V[i+1]+1==V[l]) V[i]=V[i+1]+2;
            else
            V[i]=V[i+1]+1;
        }
    }
    else
    {
        V[N]=V[l-1]+1;
        for(int i=N-1;i>l;i--) V[i]=V[i+1]+1;
    }
    for(int i=1;i<=N;i++) g<<V[i]<<" ";
    return 0;
}