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

Code

#include <iostream>
#include <vector>
#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.
*/
// Actually you can't swap the first 0 elements :(. I'm removing 1's too since it doesn't cost any extra.
std::vector<int> swaps;
BinaryTree tree;
for (int d = 0; d < l; ++d) {
tree.insert(c[d]);
int spot = tree.indexOf(c[d]);
if (spot > 1 && (swaps.size() == 0 || swaps[swaps.size() - 1] != spot)) { swaps.push_back(spot); }
if (d > 1 && (swaps.size() == 0 || swaps[swaps.size() - 1] != d)) { swaps.push_back(d); }
if (d+1 > 1 && (swaps.size() == 0 || swaps[swaps.size() - 1] != (d+1))) { swaps.push_back(d + 1); }
if (spot+1 > 1 && (swaps.size() == 0 || swaps[swaps.size() - 1] != (spot+1))) { swaps.push_back(spot + 1); }
}
std::cout << swaps.size() << "\n";
for (int i = 0; i < (int)swaps.size(); ++i) {
std::cout << swaps[i] << " ";
}
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
23
2 3 2 3 4 3 2 4 5 3 2 5 6 3 6 ...

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
3973
2 3 4 5 2 5 6 4 6 7 5 7 8 2 7 ...

Test 3

Group: 3

Verdict:

input
100000
94703 47808 62366 31885 7091 8...

correct output
399956
98676 98676 98675 98676 62994 ...

user output
399926
2 3 2 3 4 5 4 5 6 5 4 6 7 5 2 ...