the test is
1 1
the answer is obvious:)

Solved the problem using segment tree.
Im using VC++ 12 and it's giving the correct answer for the sample.
Still while sending (VC++ 2010) im getting WA 1. Changing it to G++ C++ 11 gives AC. What's the difference and why am i getting WA 1 when i choose VC++?

Code:
#include <iostream>
#include <vector>
using namespace std;
const int MAXN=100000;
pair<int, int> t[4*MAXN];
int z=1;


void build_tree(int v, int tl, int tr)
{
    if (tl==tr)
    {
        t[v]=make_pair(1,z++);
        return;
    }
    int tm=(tl+tr)/2;
    build_tree(2*v, tl, tm); build_tree(2*v+1, tm+1, tr);
    t[v].first=t[2*v].first+t[2*v+1].first;
    t[v].second=-1;
}


int req(int v, int tl, int tr, int n)
{
    if (tl==tr)
    {
        --t[v].first;
        return t[v].second;
    }
    int tm=(tl+tr)/2;
    t[v].first--;
    if (t[2*v].first>=n)
        req(2*v, tl, tm, n);
    else
        req(2*v+1, tm+1,tr,n-t[2*v].first);




}


int main()
{
    int n, k; cin>>n>>k;
    build_tree(1,1,100000);
    int cur=k;
    for (int i=0; i<n; ++i)
    {
        int h=req(1,1,100000, cur);
        cout<<h<<" ";
        if (i==n-1)
            break;
        cur=(cur-1+k)%(n-1-i);
        if (cur==0)
            cur+=n-1-i;
    }
}

Edited by author 10.03.2013 07:20

I solved using Fenwick tree and binary search for answer (:

My solution use order-statistic tree (red-black tree with additional info in nodes).
In my computer it passes test from problem description and my tests too (without crashes).

Also I have function which solve this problem in a 'naive' way (O(n^2)). I've run this function and my solution on all possible n, k: 1 <= k <= n <= 300 and results was equal (there were no craches too). I know that n, k from test1 are less than 300. So, I don't know where is my bug or it is some kind of other error.

code here:
http://acm.timus.ru/forum/thread.aspx?id=27746&upd=634623275302370098

On my tests results are the same as results of 'naive' O(n^2) solution and no crashes

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

Sorry , have found bug.

Edited by author 24.04.2009 03:03

I receive compilation error but in Borland C++ all ok.
What is problem?

#include<iostream.h>
#include<stdlib.h>
#include<string.h>

void main()
{
    unsigned long N, K, i, position;
    char * mas[30000];
    char * mas1[30000];
    char * mas2[30000];
    char * mas3[10000];

    cin>>N;
    cin>>K;


    for( i = 1 ; i <= N; i++)
    {
      if(i < 30000)
      {
        ultoa(i, mas[i - 1], 10/* size(i)*/);
      }
      else if (i < 60000)
      {
        ultoa(i,  mas1[i - 30001] , 10/* size(i)*/);
      }
      else if (i < 90000)
      {
        ultoa(i,  mas2[i - 60001] , 10/*size(i)*/);
      }
      else if (i < 100000)
      {
        ultoa(i,  mas3[i - 90001] , 10/*size(i)*/);
      }
    }

    i = 0;
    position = 0;
    int step = 0;
    while( i < N)
    {
        while(step < K)
        {
            if(position >= N)
                position = position - N;
            if(position < 30000)
            {
                if(strcmp(mas[position], "0") != 0)
                    step ++;
            }
            else if(position < 60000)
            {
                if(strcmp(mas[position - 30000], "0") != 0)
                    step ++;
            }
            else if(position < 90000)
            {
                if(strcmp(mas[position - 60000], "0") != 0)
                    step ++;
            }
            else if(position < 100000)
            {
                if(strcmp(mas[position - 90000], "0") != 0)
                    step ++;
            }
            position++;
        }
        step = 0;
        position --;
        if(position < 30000)
        {
            cout<<mas[position];
            mas[position] = "0";
        }
        else if(position < 60000)
        {
            cout<<mas1[position];
            mas1[position] = "0";
        }
        else if(position < 90000)
        {
            cout<<mas2[position];
            mas2[position] = "0";
        }
        else if(position < 100000)
        {
            cout<<mas3[position];
            mas3[position] = "0";
        }
        cout<<" ";
        i++;
        position ++;
    }
}

pls help.Can any one give the output for the above test cases
and explain why is it like that?

Can I use C++ feature "overloading of operator new" to increase the speed of memory allocation?

Should the interval tree be balanced? I use simple interval tree and get TL22.

How alogorithms with n^3/2 may be faster?

Especially to Burunduk1 :-)

How your output method is organized?
I tried different ideas. My best time is 0.078.
My algo is O( n log n ).

Maybe anyone have any ideas?

Thanks. Bye.

What is the test 5? Can you tell me where is error in my code?

[code deleted]

Edited by moderator 29.12.2006 09:26

Code in Pascal.

Edited by author 19.12.2006 12:40