Nu aveti permisiuni pentru a descarca fisierul grader_test12.ok
Cod sursa(job #2262896)
Utilizator | Data | 17 octombrie 2018 21:50:47 | |
---|---|---|---|
Problema | Order | Scor | 50 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 1.35 kb |
#include <fstream>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int N, pow = 1;
int aib[30005];
inline int LastBit(int x)
{
return x & (-x);
}
void Update(int poz, int val)
{
for(int i = poz; i <= N; i += LastBit(i))
aib[i] += val;
}
int Query(int poz)
{
int answer = 0;
for(int i = poz; i > 0; i -= LastBit(i))
answer += aib[i];
return answer;
}
int Search(int val)
{
int cursor = 0;
for(int step = pow; step > 0; step >>= 1)
if(cursor + step < N && aib[cursor + step] < val)
{
cursor += step;
val -= aib[cursor];
}
return cursor + 1;
}
int main()
{
fin >> N;
for(; pow <= N; pow <<= 1);
for(int i = 1; i <= N; i++)
Update(i, 1);
int currentPos = 1;
for(int i = 1; i <= N; i++)
{
int realSteps = i % Query(N);
if(Query(N) == 1)
realSteps = 1;
int posR = Query(N) - Query(currentPos - 1);
int posL = Query(currentPos);
int elimPos;
if(realSteps > posR)
elimPos = Search(realSteps - posR);
else
elimPos = Search(realSteps + posL);
fout << elimPos << ' ';
Update(elimPos, -1);
currentPos = elimPos;
}
return 0;
}