Cod sursa(job #1693447)

Utilizator sucureiSucureiRobert sucurei Data 23 aprilie 2016 09:01:46
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
# include <bits/stdc++.h>
using namespace std;
ifstream fi("order.in");
ofstream fo("order.out");
int s[30005];
int n;
int query(int i)
{
    int ans = 0;
    for (;i;i -= i&(-i)) ans += s[i];
    return ans;
}
void update(int i,int x)
{
    for (;i <= n;i += i&(-i)) s[i] += x;
}
int main(void)
{
    fi>>n;
    for (int i = 1;i <= n;++i) update(i,1);
    int pos = 2;
    for (int i = 1;i <= n;++i)
    {
        int k = i;
        int sum = query(n) - query(pos - 1);
        while (n - i + 1 < k) k -= n - i + 1;
        int p = pos,u = n;
        if (sum < k) k -= sum,p = 1,u = pos;
        int ans = n+1,g = p - 1;
        while (p <= u)
        {
            int m = (p+u)/2;
            if (query(m) - query(g) >= k) ans = min(ans,m),u = m - 1;else p = m + 1;
        }
        pos = ans;
        fo << ans << ' ';
        update(ans,-1);
    }
    return fo << '\n',0;
}