Cod sursa(job #2209659)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 4 iunie 2018 00:32:06
Problema Schi Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

struct thing{
    double code;
    int idx;
    bool operator<(const thing &obj)const{
        return code < obj.code;
    }
};

typedef tree<thing, null_type, less<thing>, rb_tree_tag, tree_order_statistics_node_update> Set;
int n;
Set s;

thing mkt(int idx, double code)
{
    thing aux;
    aux.code = code;
    aux.idx = idx;
    return aux;
}

int main()
{
    ifstream fin ("schi.in");
    ofstream fout ("schi.out");
    int x;
    fin >> n >> x;
    srand(time(NULL));
    s.insert(mkt(1, static_cast <double> (rand()) /( static_cast <double> (RAND_MAX/(1000000)))));
    for (int i = 2; i <= n; ++i){
        fin >> x;
        if(x == 1){
            double a1 = 0;
            double a2 = (*s.find_by_order(x-1)).code;
            s.insert(mkt(i, a1 + static_cast <double> (rand()) /( static_cast <double> (RAND_MAX/(a2-a1)))));
        }else if (x == i){
            double a1 = (*s.find_by_order(x-2)).code;
            double a2 = 1000000;
            s.insert(mkt(i, a1 + static_cast <double> (rand()) /( static_cast <double> (RAND_MAX/(a2-a1)))));
        }else{
            double a1 = (*s.find_by_order(x-2)).code;
            double a2 = (*s.find_by_order(x-1)).code;
            s.insert(mkt(i, a1 + static_cast <double> (rand()) /( static_cast <double> (RAND_MAX/(a2-a1)))));
        }
    }
    for (Set::iterator it = s.begin(); it != s.end(); ++it)
        fout << it->idx << "\n";
    return 0;
}