When i use bubble alg i have TLE #5(it's normal, i understand that), but when i use quick sort, i have WA#3, why??? What is wrong?

Edited by author 15.12.2011 23:01

my bulky code:


#include <iostream>


class RedBlackTreeWithoutRepeatedElements {

  private:

    static const int BAD_KEY = - 1;

    static enum TypeOfRotation {LEFT, RIGHT};

    static enum NodeColor {RED, BLACK};

    struct Node {

      int key;
      Node *left, *right, *parent;
      NodeColor color;
      int total_number_of_nodes_in_subtree_with_this_node_as_root;

      Node(int m_key) : key(m_key),
                        left(NULL), right(NULL), parent(NULL),
                        color(RED),
                        total_number_of_nodes_in_subtree_with_this_node_as_root(1) {}
    };

    Node *root_, *nil_delimiter;


    void inorderedWalkWithNodeDeletion(Node *node) {
      if ( node != nil_delimiter ) {
        inorderedWalkWithNodeDeletion(node->left);
        Node *root_of_right_subtree = node->right;
        delete node;
        inorderedWalkWithNodeDeletion(root_of_right_subtree);
      }
    }


    void rotate(Node *node, TypeOfRotation type_of_rotation) {

      if ( node == nil_delimiter ) {
        return;
      }

      Node *substitutor_node = (type_of_rotation == LEFT) ? node->right : node->left;
      if ( node == nil_delimiter ) {
        return;
      }

      if ( type_of_rotation == LEFT ) {
        node->right = substitutor_node->left;
        if ( substitutor_node->left != nil_delimiter ) {
          substitutor_node->left->parent = node;
        }
        substitutor_node->left = node;
      }
      else {
        node->left = substitutor_node->right;
        if ( substitutor_node->right != nil_delimiter ) {
          substitutor_node->right->parent = node;
        }
        substitutor_node->right = node;
      }

      substitutor_node->parent = node->parent;
      if ( node != root_ ) {
        if ( node == node->parent->left ) {
          node->parent->left = substitutor_node;
        }
        else {
          node->parent->right = substitutor_node;
        }
      }
      else {
        root_ = substitutor_node;
      }
      node->parent = substitutor_node;

      substitutor_node->total_number_of_nodes_in_subtree_with_this_node_as_root =
        node->total_number_of_nodes_in_subtree_with_this_node_as_root;
      node->total_number_of_nodes_in_subtree_with_this_node_as_root =
        node->left->total_number_of_nodes_in_subtree_with_this_node_as_root +
        node->right->total_number_of_nodes_in_subtree_with_this_node_as_root + 1;
    }


    void correctPropertiesOfRedBlackTreeAfterInsertion(Node *node) {

      while ( node->parent->color == RED ) {

        Node *grandparent_node = node->parent->parent;

        Node *uncle_node = (node->parent == grandparent_node->left) ?
          grandparent_node->right : grandparent_node->left;

        if ( uncle_node->color == RED ) {
          uncle_node->color = node->parent->color = BLACK;
          grandparent_node->color = RED;
          node = grandparent_node;
        }
        else {

          if ( node->parent == grandparent_node->left ) {
            if ( node == node->parent->right ) {
              rotate(node->parent, LEFT);
              node = node->left;
            }
          }
          else {
            if ( node == node->parent->left ) {
              rotate(node->parent, RIGHT);
              node = node->right;
            }
          }

          node->parent->color = BLACK;
          grandparent_node->color = RED;
          rotate(grandparent_node, (node->parent == grandparent_node->left) ? RIGHT : LEFT );
        }
      }

      root_->color = BLACK;
    }


    void correctPropertiesOfRedBlackTreeAfterDelettion(Node *node) {

      while ( node != root_ && node->color == BLACK ) {

        if ( node == node->parent->left ) {

          Node *sibling_node = node->parent->right;

          if ( sibling_node->color == RED ) {
            sibling_node->color = BLACK;
            node->parent->color = RED;
            rotate(node->parent, LEFT);
            sibling_node = node->parent->right;
          }

          if ( sibling_node->left->color == BLACK && sibling_node->right->color == BLACK ) {
            sibling_node->color = RED;
            node = node->parent;
          }
          else {

            if ( sibling_node->right->color == BLACK ) {
              sibling_node->left->color = BLACK;
              sibling_node->color = RED;
              rotate(sibling_node, RIGHT);
              sibling_node = node->parent->right;
            }

            sibling_node->color = node->parent->color;
            node->parent->color = BLACK;
            sibling_node->right->color = BLACK;
            rotate(node->parent, LEFT);
            node = root_;
          }
        }
        else {

          Node *sibling_node = node->parent->left;

          if ( sibling_node->color == RED ) {
            sibling_node->color = BLACK;
            node->parent->color = RED;
            rotate(node->parent, RIGHT);
            sibling_node = node->parent->left;
          }

          if ( sibling_node->left->color == BLACK && sibling_node->right->color == BLACK ) {
            sibling_node->color = RED;
            node = node->parent;
          }
          else {

            if ( sibling_node->left->color == BLACK ) {
              sibling_node->right->color = BLACK;
              sibling_node->color = RED;
              rotate(sibling_node, LEFT);
              sibling_node = node->parent->left;
            }

            sibling_node->color = node->parent->color;
            node->parent->color = BLACK;
            sibling_node->left->color = BLACK;
            rotate(node->parent, RIGHT);
            node = root_;
          }
        }
      }

      node->color = BLACK;
    }


    void removeNode(Node *node) {

      Node *node_to_be_actually_deleted;

      if ( node->left == nil_delimiter || node->right == nil_delimiter ) {
        node_to_be_actually_deleted = node;
      }
      else {
        node_to_be_actually_deleted = node->right;
        while ( node_to_be_actually_deleted->left != nil_delimiter ) {
          node_to_be_actually_deleted = node_to_be_actually_deleted->left;
        }
      }

      --node_to_be_actually_deleted->total_number_of_nodes_in_subtree_with_this_node_as_root;
      Node *current_node = node_to_be_actually_deleted->parent;
      while ( current_node != nil_delimiter ) {
        --current_node->total_number_of_nodes_in_subtree_with_this_node_as_root;
        current_node = current_node->parent;
      }

      Node *only_child_of_node_to_be_actually_deleted =
        (node_to_be_actually_deleted->left != nil_delimiter) ? node_to_be_actually_deleted->left :
                                                               node_to_be_actually_deleted->right;

      only_child_of_node_to_be_actually_deleted->parent =
        node_to_be_actually_deleted->parent;

      if ( node_to_be_actually_deleted->parent != nil_delimiter ) {
        if ( node_to_be_actually_deleted == node_to_be_actually_deleted->parent->left ) {
          node_to_be_actually_deleted->parent->left = only_child_of_node_to_be_actually_deleted;
        }
        else {
          node_to_be_actually_deleted->parent->right = only_child_of_node_to_be_actually_deleted;
        }
      }
      else {
        root_ = only_child_of_node_to_be_actually_deleted;
      }

      if ( node != node_to_be_actually_deleted ) {
        node->key = node_to_be_actually_deleted->key;
      }

      if ( node_to_be_actually_deleted->color == BLACK ) {
        correctPropertiesOfRedBlackTreeAfterDelettion(only_child_of_node_to_be_actually_deleted);
      }

      delete node_to_be_actually_deleted;
    }


    Node* find_k_th_element(int k, Node *root_of_subtree) {

      int r = root_of_subtree->left->total_number_of_nodes_in_subtree_with_this_node_as_root + 1;

      if ( r == k ) {
        return root_of_subtree;
      }
      else if ( r > k ) {
        find_k_th_element(k, root_of_subtree->left);
      }
      else {
        find_k_th_element(k - r, root_of_subtree->right);
      }
    }


  public:

    RedBlackTreeWithoutRepeatedElements() {
      nil_delimiter = new Node(BAD_KEY);
        nil_delimiter->color = BLACK;
        nil_delimiter->left = nil_delimiter->right = nil_delimiter;
        nil_delimiter->total_number_of_nodes_in_subtree_with_this_node_as_root = 0;
      root_ = nil_delimiter;
    }


    void insert(int new_key) {

      if ( root_ == nil_delimiter ) {
        root_ = new Node(new_key);
          root_->color = BLACK;
          root_->left = root_->right = root_->parent = nil_delimiter;
        return;
      }

      Node *current_node = root_, *parent_node = nil_delimiter, *new_node = new Node(new_key);
        new_node->left = new_node->right = nil_delimiter;

      while ( current_node != nil_delimiter ) {
        ++current_node->total_number_of_nodes_in_subtree_with_this_node_as_root;
        parent_node = current_node;
        current_node = (current_node->key > new_key) ? current_node->left : current_node->right;
      }

      if ( parent_node->key > new_key ) {
        parent_node->left = new_node;
      }
      else {
        parent_node->right = new_node;
      }
      new_node->parent = parent_node;

      correctPropertiesOfRedBlackTreeAfterInsertion(new_node);
    }


    int getKeyOfKthElementAndRemoveIt(int k) {
      Node *k_th_element = find_k_th_element(k, root_);
      int key_of_k_th_element = k_th_element->key;
      removeNode(k_th_element);
      return key_of_k_th_element;
    }


    int getSize() const {
      return (root_ != nil_delimiter) ?
        root_->total_number_of_nodes_in_subtree_with_this_node_as_root : 0;
    }


    ~RedBlackTreeWithoutRepeatedElements() {
      inorderedWalkWithNodeDeletion(root_);
      delete nil_delimiter;
    }
};



int main() {

  int number_of_soldiers, number_of_words_in_counting_out_rhyme;

  std::cin >> number_of_soldiers >> number_of_words_in_counting_out_rhyme;

  RedBlackTreeWithoutRepeatedElements soldiers;

  for ( int soldier_id = 1; soldier_id <= number_of_soldiers; ++soldier_id ) {
    soldiers.insert(soldier_id);
  }


   int start_position_for_counting = 1, position_of_excluded_solider;

    while ( soldiers.getSize() > 1 ) {
      position_of_excluded_solider =
        start_position_for_counting + number_of_words_in_counting_out_rhyme - 1;
      if ( position_of_excluded_solider > soldiers.getSize() ) {
        position_of_excluded_solider =
          (number_of_words_in_counting_out_rhyme -
            (soldiers.getSize() - start_position_for_counting + 1)) % soldiers.getSize();
        if ( position_of_excluded_solider == 0 ) {
          position_of_excluded_solider = soldiers.getSize();
        }
      }
      std::cout << soldiers.getKeyOfKthElementAndRemoveIt(position_of_excluded_solider) << " ";
      start_position_for_counting = (position_of_excluded_solider <= soldiers.getSize()) ?
        position_of_excluded_solider : 1;
    }

    std::cout << soldiers.getKeyOfKthElementAndRemoveIt(1);

#if !defined(ONLINE_JUDGE)
  std::cin.ignore(std::cin.rdbuf()->in_avail());
  std::cin.get();
#endif

  return 0;
}


Edited by author 16.01.2012 16:24

Edited by author 16.01.2012 16:39

Hi, I'm using grundy numbers for this problems, however I get WA 5.

#include <cstdio>
#include <cstring>

using namespace std;

int n[50],a[50][100];
int g[50][100][100];

int main(){
    int K;

    scanf("%d",&K);

    for(int i = 0;i < K;++i){
        scanf("%d",&n[i]);

        for(int j = 0;j < n[i];++j)
            scanf("%d",&a[i][j]);
    }

    memset(g,0,sizeof g);

    bool have[201];

    for(int k = 0;k < K;++k){
        for(int l = 1;l <= n[k];++l){
            for(int i = 0;i + l <= n[k];++i){
                memset(have,false,sizeof have);

                for(int j = i;j < i + l;++j){
                    int x = a[k][j],sum = 0;

                    for(int s = i;s < i + l;){
                        if(a[k][s] <= x) ++s;
                        else{
                            int e = s;

                            while(e < i + l && a[k][e] > x) ++e;

                            sum ^= g[k][s][e - 1];
                            s = e + 1;
                        }
                    }

                    have[sum] = true;
                }

                while(have[ g[k][i][i + l - 1] ])
                    ++g[k][i][i + l - 1];
            }
        }
    }

    int G = 0;

    for(int k = 0;k < K;++k)
        G ^= g[k][0][n[k] - 1];

    if(G){
        puts("G");

        bool found = false;

        for(int k = 0;k < K && !found;++k){
            for(int i = 0;i < n[k] && !found;++i){
                G = 0;

                for(int j = 0;j < K;++j)
                    if(j != k)
                        G ^= g[k][0][n[j] - 1];

                int x = a[k][i],sum = 0;

                for(int s = 0;s < n[k];){
                    if(a[k][s] <= x) ++s;
                    else{
                        int e = s;

                        while(e < n[k] && a[k][e] > x) ++e;

                        G ^= g[k][s][e - 1];
                        s = e + 1;
                    }
                }

                if(G == 0){
                    found = true;
                    printf("%d %d\n",k + 1,i + 1);
                }
            }
        }
    }else puts("S");



    return 0;
}

this is not Edited
Edited by author 22.01.2012 12:31

Edited by author 22.01.2012 12:31

if n or p or T or V not integer then error or some value?

Edited by author 15.01.2012 05:32

help

Edited by author 08.04.2012 20:51

#include <iostream>
using namespace std;
int main()
{
    double a,b,c,d;
    cin >> a >> b >> c >> d;

    cout << sqrt(d) << endl
        << sqrt(c) << endl
        << sqrt(b) << endl
        << sqrt(a) << endl;

    return 0;
}

why?

#include <iostream>
#include <cmath>
using namespace std;
#define SWAP(A, B) { int t = A; A = B; B = t; }

void bubblesort(int *a, int n)
{
  int i, j;

  for (i = n - 1; i > 0; i--)
  {
    for (j = 0; j < i; j++)
    {
      if (a[j] > a[j + 1])
        SWAP( a[j], a[j + 1] );
    }
  }
}
int main()
{
int n,x,ar[100];
cin>>n>>x;
for(int i=0;i<n;i++)
cin>>ar[i];
bubblesort(ar,n);
int j=0;
while(ar[j]<0 && j<n-1)
    ++j;
if(ar[j-1]<x && ar[j]>x && n!=1 )
{
    if(x<0)
    cout<<2*ar[j]-x<<" "<<0-x;
    else
        cout<<x<<" "<<abs(2*ar[j-1])+x;
}
else
    if(n==1)
    {
    if(ar[0] > x)
        cout<<2*abs(ar[0])-x<<" "<<-x;
    else
        cout<<x<<" "<<2*abs(ar[0])+x;
    }
    else
    cout<<"Impossible";
}

It is "antiquicksort" test. Use pivot differ from (bottom + top) / 2, for example, random choosed.

AC 0.031 s. 156 Kb.

Edited by author 14.01.2012 18:16

Edited by author 14.01.2012 18:18

I used q_sort and have time limit 15?
And I used stl sort and got AC.
Decides it is problem with Q_sort?

program order;
var n,ap,i,j:longint;
    x:array[1..10000] of real;
    begin
    readln(n);
    for i:=1 to n do
    readln(x[i]);
    i:=1;
    while i<=n do begin
    ap:=1;
    for j:=i+1 to n do
    if x[i]=x[j] then ap:=ap+1;
    if ap>(n div 2) then begin writeln(x[i]:0:0);
                         break;
                         end
              else i:=i+1;
              end;
              end.

program p1207;
uses math;
type
  realer=record
           rr:real;
           num:longint;
         end;
var
  i,j,k,n,m,x,y,x0,y0:longint;
  r:array[1..10000]of realer;
procedure qs(h,t:longint);
  var
    i,j:longint;
    k:real;
    o:realer;
  begin
    if h>=t
      then exit;
    i:=h;j:=t;k:=r[(i+j)div 2].rr;
    repeat
      while r[i].rr<k do
        inc(i);
      while r[j].rr>k do
        dec(j);
      if i<=j
        then begin
          o:=r[i];
          r[i]:=r[j];
          r[j]:=o;
          inc(i);
          dec(j);
        end;
    until i>j;
    qs(h,j);
    qs(i,t);
  end;
begin
  readln(n);
  readln(x0,y0);
  for i:=2 to n do
    begin
      readln(x,y);
      x:=x-x0;
      y:=y-y0;
      if x=0
        then
          if y>0
            then r[i-1].rr:=0.5*pi
            else r[i-1].rr:=-0.5*pi
        else r[i-1].rr:=arctan(y/x);
      r[i-1].num:=i;
    end;
  qs(1,n-1);
  writeln(1,' ',r[n div 2].num);
end.

Segment tree can help solve the problem. I've got AC 0.046s 512Kb.
My steps:
1. Read all input and build segment tree
2. Get rmq(i, i + m - 1) for all needed i

Look, using the theorem we could build a triangle with such vertexes:
NO
-1.0000000000 4.0000000000
0.0000000000 0.0000000000
-0.8780487805 3.9024390244
(img: http://ge.tt/9klV3HC/v/0 )

hiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii