CSES - Datatähti 2017 alku - Results
Submission details
Task:Järjestys
Sender:mangolassi
Submission time:2016-10-03 20:41:49 +0300
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.06 s1details
#20.06 s2details
#30.17 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.
  */
  BinaryTree tree;
  for (int d = 0; d < l; ++d) {
    tree.insert(c[d]);
    int spot = tree.indexOf(c[d]);
    std::cout << spot << " ";
    std::cout << d << " ";
    std::cout << (d + 1) << " ";
    std::cout << (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
0 0 1 1 
0 1 2 1 
1 2 3 2 
2 3 4 3 
2 4 5 3 
...

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
0 0 1 1 
1 1 2 2 
2 2 3 3 
0 3 4 1 
1 4 5 2 
...

Test 3

Group: 3

Verdict:

input
100000
94703 47808 62366 31885 7091 8...

correct output
399956
98676 98676 98675 98676 62994 ...

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