Mai intai trebuie sa te autentifici.
Cod sursa(job #2013841)
Utilizator | Data | 22 august 2017 15:09:24 | |
---|---|---|---|
Problema | Order | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.44 kb |
//Se foloseste stiva S pt a retine elementele care vor trebui eliminate
#include<fstream>
#include<stack>
using namespace std;
ifstream fi("order.in");
ofstream fo("order.out");
int n,i,ind,poz,ramas,F[30001];
stack<int> S;
void update(int poz, int val)
{
while(poz<=n)
{
F[poz]+=val;
poz=poz+(poz&(poz^(poz-1)));
}
}
int f(int poz)
{
int rez=0;
while(poz>0)
{
rez+=F[poz];
poz=poz-(poz&(poz^(poz-1)));
}
return rez;
}
int query(int st, int dr)
{
return f(dr)-f(st-1);
}
int bs(int val)
{
int st=1,dr=n,mij;
while(st<=dr)
{
mij=(st+dr)/2;
int k=query(1,mij);
if(val<=k)
{
dr=mij-1;
}
else
{
st=mij+1;
}
}
return st;
}
int main()
{
fi>>n;
ramas=n;
ind=1;
for(i=1; i<=n; i++)
update(i,1);
for(i=1; i<=n; i++)
{
ind=ind+i;
if(ind>ramas)
{
ind=ind-ramas;
while(!S.empty())
{
update(S.top(),-1);
S.pop();
ramas--;
}
ind=ind%ramas;
if(ind==0)
ind=ramas;
}
poz=bs(ind);
fo<<poz<<" ";
S.push(poz);
//update(poz,-1);
}
fo<<"\n";
fi.close();
fo.close();
return 0;
}