Cod sursa(job #2924086)

Utilizator StefanL2005Stefan Leustean StefanL2005 Data 24 septembrie 2022 22:54:03
Problema Schi Scor 35
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;
ifstream in("schi.in");
ofstream out("schi.out");

int Sum(vector< int > O, vector< int > S_O, int a, int k)
{
    int cat = a / k, r = a % k;
    int s = 0;

    for (int i = 0; i < cat; i++)
        s += S_O[i];

    for (int i = cat * k; i <= cat * k + r; i++)
        if (O[i] != -1)
            s++;

    return s;

}

void find_current_pos(int n, int k, int nr, int pos, vector< int > &O, vector< int > &S_O)
{
    int c1;
    c1 = Sum(O, S_O, nr - 1, k);

    if (O[nr - 1] == -1 && c1 == 0)
    {
        O[nr - 1] = pos;
        S_O[nr / k]++;
    }
    else
    {
        int N, c2;
        N = c1 + nr - 1;
        c2 = Sum(O, S_O, N, k);

        while ( c2 != c1 )
        {
            c1 = c2;
            N = c2 + nr - 1;
            c2 = Sum(O, S_O, N, k);
        }

        O[N] = pos;
        S_O[N / k]++;
    }

}
int main()
{
    int n, k;
    in>> n;
    vector< int > v(n);
    k = sqrt(n);

    for (int i = 0; i < n; i++)
        in>> v[i];

    vector< int > O(n, -1), S_O(n / k + 1, 0);

    for (int i = n - 1; i >= 0; i--)
        find_current_pos(n, k, v[i], i, O, S_O);

    for (int i = 0; i < n; i++)
        out<< O[i] + 1 << "\n";
    return 0;
}