Cod sursa(job #2751438)

Utilizator realmeabefirhuja petru realmeabefir Data 14 mai 2021 23:48:55
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

ifstream f("order.in");
ofstream g("order.out");

int main()
{
    int n;
    f >> n;
    int rad = sqrt(n);

    int dim_smen = n/rad+1;
    if (rad*rad == n)
        dim_smen--;

    int smen[dim_smen];
    int smen_size[dim_smen];
    int v[n];
    for (int i = 0; i < dim_smen; i++)
        smen[i] = 0;

    for (int i = 0; i < n; i++)
    {
        v[i] = 1;
        int poz_in_smen = i / rad;
        smen[poz_in_smen] ++;
        smen_size[poz_in_smen] ++;
    }

    int i_cur = 1;
    v[1] = 0;
    int tmp = 1/rad;
    smen[tmp] --;
    g << 2 << ' ';
    for (int i = 1; i < n; i++)
    {
        int j = i;
        while (j != 0)
        {
            // veriic daca este la inceputul unei portiuni de smen (idk)
            if (i_cur % rad == 0)
            {
                int i_smen = i_cur/rad;
                // daca putem adauga valoarea din smen fara sa trecem peste
                if (j - smen[i_smen] >= 0)
                {
                    j -= smen[i_smen];
                    i_cur += smen_size[i_smen];
                    i_cur = i_cur % n;
                } else
                {
                    if (v[i_cur] == 1)
                    {
                        j -= 1;
                    }
                    i_cur ++;
                    i_cur = i_cur % n;
                }
            }
            // daca nu e la ineput de portiune de smen luam unu cate unu
            else
            {
                if (v[i_cur] == 1)
                {
                    j -= 1;
                }
                i_cur ++;
                i_cur = i_cur % n;
            }
        }
        // scadem din vector si din smen la i_cur
        while (v[i_cur] != 1)
        {
            i_cur += 1;
            i_cur = i_cur % n;
        }
        v[i_cur] -= 1;

        int poz_smen = i_cur / rad;
        smen[poz_smen] --;

        g << i_cur + 1 << ' ';
        #if 0
            cout << i_cur << '\n';
            for (int i = 0; i < n; i++)
                cout << v[i] << ' ';
            cout << '\n';
            for (int i = 0; i < n; i++)
            {
                int poz_smen = i / rad;
                cout << smen[poz_smen] << ' ';
            }
            cout << '\n';
        #endif


    }

    return 0;
}