Pagini recente » Cod sursa (job #1164276) | Cod sursa (job #2403877) | Cod sursa (job #2874813) | Cod sursa (job #1108236) | Cod sursa (job #147818)
Cod sursa(job #147818)
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
int N;
/*class Node {
public:
Node(int _n) :
n(_n),
next(0)
{
}
int n;
Node *next;
};
class Group {
public:
Group() :
firstChild(-1),
next(0),
count(0)
{
}
Node firstChild;
Group *next;
int count;
};
Group groups;
void buildList() {
int gs = sqrt(N);
Group *cur = &groups;
int k(0);
for (int i(0); i <= gs; ++i) {
if (k == N)
break;
cur->next = new Group();
cur = cur->next;
Node *curn = &cur->firstChild;
for (int j = i * gs; (j <= (i + 1) * gs) && (k < N); ++j, ++k) {
curn->next = new Node(k + 1);
curn = curn->next;
++cur->count;
}
}
cur->next = groups.next;
// cur = groups.next;
// while (cur) {
// cout << cur->count << ": ";
// Node *curn = cur->firstChild.next;
// while (curn) {
// cout << curn->n << " ";
// curn = curn->next;
// }
// cout << endl;
// cur = cur->next;
//}
}
void listCut() {
FILE *fout = fopen("order.out", "w");
Group *curg = groups.next;
Node *curn = curg->firstChild.next;
int indgroup(0);
int cut(0);
int skip(1);
while (cut < N) {
int nows = indgroup + skip++;
//cout << "nows: " << nows << endl;
while (nows >= curg->count) {
//cout << "Skipping group..." << endl;
nows -= curg->count;
curg = curg->next;
}
indgroup = nows;
curn = &(curg->firstChild);
Node *p;
for (int i(0); i <= indgroup; ++i) {
p = curn;
curn = curn->next;
}
p->next = curn->next;
--curg->count;
fprintf(fout, "%d ", curn->n);
--indgroup;
++cut;
}
fprintf(fout, "\n");
fclose(fout);
}*/
int T[128000];
int build_tree(int st, int dr, int cur) {
if (st == dr)
return T[cur] = 1;
int q = (st + dr) / 2;
T[cur] = build_tree(st, q, cur*2) +
build_tree(q + 1, dr, cur*2+1);
return T[cur];
}
int find_and_cut_nth(int n, int st, int dr, int cur) {
//cout << st << "-" << dr << endl;
--T[cur];
if (st == dr)
return st;
int q = (st + dr) / 2;
int b;
if (n > T[cur*2])
b = find_and_cut_nth(n - T[cur*2], q + 1, dr, cur*2+1);
else
b = find_and_cut_nth(n, st, q, cur*2);
return b;
}
void print_tree(int st, int dr, int cur = 1, int d = 0) {
if (!T[cur])
return;
for (int i(0); i < d; ++i)
cout << " ";
cout << st << " - " << dr << ":\t\t" << T[cur] << endl;
print_tree(st, (st+dr)/2, cur*2, d+1);
print_tree((st+dr)/2+1, dr, cur*2+1, d+1);
}
void chop_it() {
int cur = 2;
int skip = 1;
FILE *fo = fopen("order.out", "w");
while (T[1]) {
fprintf(fo, "%d ", find_and_cut_nth(cur, 1, N, 1));
if (T[1]) {
cur = (cur + skip) % T[1];
if (!cur)
cur = T[1];
}
++skip;
}
fprintf(fo, "\n");
fclose(fo);
}
int main(int argc, char *argv[]) {
ifstream fin("order.in");
fin >> N;
fin.close();
//buildList();
//listCut();
build_tree(1, N, 1);
chop_it();
return 0;
}