CSES - Datatähti 2017 alku - Results
Submission details
Task:Järjestys
Sender:mangolassi
Submission time:2016-10-03 20:46:19 +0300
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.06 s1details
#20.05 s2details
#30.16 s3details

Code

#include <iostream>
#include <algorithm>
// Augmented binary tree for better average case time complexity.
// Hopefully no inputs are inoptimal. I really don't want to make
// this a red-black tree.
struct Node {
int value;
int lc;
int rc;
Node* left;
Node* right;
Node(int v) {
value = v;
lc = 0;
rc = 0;
left = 0;
right = 0;
}
};
struct BinaryTree {
Node* root;
BinaryTree() {
root = 0;
}
void insert(int i) {
Node* node = new Node(i);
if (root == 0) {
root = node;
return;
}
Node* n = root;
while(true) {
if (n->value < i) {
++n->rc;
if (n->right == 0) {
n->right = node;
break;
} else {
n = n->right;
}
} else if (n->value >= i) {
++n->lc;
if (n->left == 0) {
n->left = node;
break;
} else {
n = n->left;
}
}
}
}
int indexOf(int i) {
if (root == 0) {
return 0;
}
Node* n = root;
int index = 0;
while(true) {
if (i == n->value) {
return index;
}
if (i < n->value) {
n = n->left;
} else if (i > n->value) {
index += n->lc + 1;
n = n->right;
}
}
}
};
int main() {
int l;
std::cin >> l;
int* c = new int[l];
for (int i = 0; i < l; ++i) {
int n;
std::cin >> n;
c[i] = n;
}
/*
Insertion sort-ish
0: (a-b)-(c-d)-e-f || Step 1: swap elements before new one's spot
1: (b-a)-(c-d)-e-f || Step 2: swap elements before new one
2: (d-c)-(a-b)-e-f || Step 3: swap elements before new one, and new one
3: e-(b-a)-(c-d)-f || Step 4: Swap elements before new one's spot and the spot
4: (a-b)-e-(c-d)-f || DONE!
However, finding the position we need to insert e to is an o(n) operation.
So I'll use this augmented binary tree to find the new one's position.
*/
std::cout << l * 4 << "\n";
BinaryTree tree;
for (int d = 0; d < l; ++d) {
tree.insert(c[d]);
int spot = tree.indexOf(c[d]);
std::cout << spot << " " << d << " " << (d + 1) << " " << (spot + 1) << " ";
}
std::cout << "\n";
}

Test details

Test 1

Group: 1

Verdict:

input
10
9 3 4 7 6 5 10 2 8 1

correct output
32
10 10 9 10 9 8 7 9 4 2 1 4 5 2...

user output
40
0 0 1 1 0 1 2 1 1 2 3 2 2 3 4 ...

Test 2

Group: 2

Verdict:

input
1000
650 716 982 41 133 1000 876 92...

correct output
3984
207 207 206 207 128 127 126 12...

user output
4000
0 0 1 1 1 1 2 2 2 2 3 3 0 3 4 ...

Test 3

Group: 3

Verdict:

input
100000
94703 47808 62366 31885 7091 8...

correct output
399956
98676 98676 98675 98676 62994 ...

user output
400000
0 0 1 1 0 1 2 1 1 2 3 2 0 3 4 ...