Pagini recente » Cod sursa (job #1019026) | Cod sursa (job #2606133) | Cod sursa (job #539592) | Cod sursa (job #2425035) | Cod sursa (job #145811)
Cod sursa(job #145811)
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
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;
};
int N;
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 main(int argc, char *argv[]) {
ifstream fin("order.in");
fin >> N;
fin.close();
buildList();
listCut();
return 0;
}