Pagini recente » Cod sursa (job #1636123) | Clasament alex001 | Cod sursa (job #2461503) | Cod sursa (job #287558) | Cod sursa (job #1939628)
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <ctime>
class OutParser {
private:
FILE *fout;
char *buff;
int sp;
void write_ch(char ch) {
if (sp == 50000) {
fwrite(buff, 1, 50000, fout);
sp = 0;
buff[sp++] = ch;
} else {
buff[sp++] = ch;
}
}
public:
OutParser(const char* name) {
fout = fopen(name, "w");
buff = new char[50000]();
sp = 0;
}
~OutParser() {
fwrite(buff, 1, sp, fout);
fclose(fout);
}
OutParser& operator << (int vu32) {
if (vu32 <= 9) {
write_ch(vu32 + '0');
} else {
(*this) << (vu32 / 10);
write_ch(vu32 % 10 + '0');
}
return *this;
}
OutParser& operator << (long long vu64) {
if (vu64 <= 9) {
write_ch(vu64 + '0');
} else {
(*this) << (vu64 / 10);
write_ch(vu64 % 10 + '0');
}
return *this;
}
OutParser& operator << (char ch) {
write_ch(ch);
return *this;
}
OutParser& operator << (const char *ch) {
while (*ch) {
write_ch(*ch);
++ch;
}
return *this;
}
};
OutParser fout("order.out");
struct Node {
int val;
int size;
int priority;
Node* left;
Node* right;
bool reversed;
};
Node* emptyNode = new Node{0, 0, -1, NULL, NULL, false};
void unreverse(Node* root) {
if (root != emptyNode && root->reversed) {
std::swap(root->left, root->right);
root->left->reversed = !root->left->reversed;
root->right->reversed = !root->right->reversed;
root->reversed = false;
}
}
void recompute(Node* root) {
root->size = root->left->size + 1 + root->right->size;
}
std::pair<Node*, Node*> split(Node* root, int k) {
unreverse(root);
std::pair<Node*, Node*> answer;
if (root == emptyNode) {
answer.first = emptyNode;
answer.second = emptyNode;
} else if (k <= root->left->size) {
answer.second = root;
auto p = split(root->left, k);
answer.first = p.first;
answer.second->left = p.second;
recompute(answer.second);
} else {
answer.first = root;
auto p = split(root->right, k - root->left->size - 1);
answer.first->right = p.first;
recompute(answer.first);
answer.second = p.second;
}
return answer;
}
Node* join(Node* root1, Node* root2) {
unreverse(root1);
unreverse(root2);
if (root1 == emptyNode) {
return root2;
} else if (root2 == emptyNode) {
return root1;
} else if (root1->priority > root2->priority) {
root1->right = join(root1->right, root2);
recompute(root1);
return root1;
} else {
root2->left = join(root1, root2->left);
recompute(root2);
return root2;
}
}
Node* insert(Node* root, int k, Node* val) {
auto p = split(root, k - 1);
return join(join(p.first, val), p.second);
}
Node* insert(Node* root, int k, int val) {
return insert(root, k, new Node{val, 1, rand(), emptyNode, emptyNode, false});
}
Node* erase(Node* root, int k) {
auto p1 = split(root, k - 1);
auto p2 = split(p1.second, 1);
fout << p2.first->val << ' ';
delete p2.first;
return join(p1.first, p2.second);
}
int main() {
freopen("order.in", "r", stdin);
srand(time(0));
int N;
scanf("%d", &N);
Node* root = emptyNode;
for (int i = 1; i <= N; ++i)
root = insert(root, i, i);
int start = 1, copie = N;
for (; N >= 1; --N) {
start = (start + (copie - N + 1)) % N;
if (start == 0)
start = N;
root = erase(root, start);
start--;
if (start == 0)
start = N - 1;
}
return 0;
}