Pagini recente » Diferente pentru monthly-2014/runda-6/solutii intre reviziile 8 si 4 | Istoria paginii utilizator/murzacion | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #996880)
Cod sursa(job #996880)
#include <fstream>
using namespace std;
const int MAX_N = 30002;
int N;
int A[MAX_N];
inline void Update(int pos, int val) {
while(pos <= N) {
A[pos] += val;
pos += pos^(pos&(pos-1));
}
}
inline int Query(int pos) {
int Sum = 0;
while(pos > 0) {
Sum += A[pos];
pos -= pos^(pos&(pos-1));
}
return Sum;
}
int main() {
ifstream f("order.in");
ofstream g("order.out");
f >> N;
for(int i = 1; i <= N; ++i)
Update(i, 1);
g << 2 << " ";
Update(2, -1);
int m = 0;
for(int i = 2, now = 2; i <= N; ++i) {
int k = N-i+1, temp = Query(now), s = 0;
int x = i%k, l, r, t = 0;
if(!x)
x = k;
if(x > k - temp)
x -= k-temp, l = 1, r = now - 1;
else l = now + 1, r = N, s = temp;
while(l <= r) {
m = (l+r)/2;
if(Query(m) - s >= x)
r = m-1, t = m;
else l = m+1;
}
now = t;
Update(t, -1);
g << t << " ";
}
g << "\n";
f.close();
g.close();
return 0;
}