Cod sursa(job #1461461)

Utilizator cojocarugabiReality cojocarugabi Data 15 iulie 2015 19:15:50
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
# include <bits/stdc++.h>
using namespace std;
ifstream fi("order.in");
ofstream fo("order.out");
int s[30005],n;
int l[305],d[305],p[30005],pre[30005];
int main(void)
{
    fi>>n;
    int r = sqrt(n);
    if (n == 1) return fo << "1\n",0;
    int k = 0;
    for (int i = 1;i <= n;++i)
    {
        pre[i] = i - 1;
        if (!pre[i]) pre[i] = n;
        if ((i%r) == 1) ++k;
        p[i] = k;++l[k];
    }
    int cnt = 2;
    for (int i = 1;i < n;++i)
    {
        int pl = i;
        while ((cnt % r != 1) && (pl + s[cnt] > 0))
        {
            --pl;pl += s[cnt];++cnt;
            if (cnt == n + 1) cnt = 1;
        }
        int fr = p[cnt];
        while (pl && pl + d[fr] >= l[fr])
        {
            pl += d[fr];pl -= l[fr];cnt += l[fr];++fr;
            if (cnt == n + 1) cnt = 1;
            if (fr == k+1) fr = 1;
        }
        while (pl + s[cnt] > 0)
        {
            --pl;pl += s[cnt];++cnt;
            if (cnt == n+1) cnt = 1;
        }
        cnt = pre[cnt];
        s[cnt] = 1;
        d[p[cnt]] += 1;
        if (cnt == n) pre[1] = pre[n];
        else pre[cnt+1] = pre[cnt];
        fo << cnt << ' ';
    }
    for (int i = 1;i <= n;++i) if (!s[i]) fo << i << '\n';
    return fo << '\n',0;
}