458 Order 2

[•filipb]

Aici puteţi discuta despre problema Order 2.

[•pauldb]

Poate ar fi mai interesant la problema asta sa se ofere punctajul si in functie de numarul de mutari.
Eu m-am gandit la ceva de genul 100-([X/N]-2)*20, unde x e numarul de mutari. Voi ce spuneti?

[•pauldb]

Daca nu ma insel, ultimele 3 teste au N>1000.   

[•devilkind]

  s-a corectat

[•GabiTulba]

Imi poate spune cineva cum trebuie rezolvata problema? Adica... rezolvata pentru mai putin de 2N+1 operatii.
Pentru 2N+1 operatii am rezolvat-o si nu stiu cum altfel sa o abordez.
Help!
Aici este codul meu:

#include <iostream>
#include <fstream>

using namespace std;

ifstream in("order2.in");
ofstream out ("order2.out");

int N,sort[2002],arr[2002];

int part(int *arr,int start,int end)
{
   int index=start,piv=arr[end],t;
   for(int i=start;i<=end;i++)
      if(arr<=piv)
      {
         t=arr;
         arr=arr[index];
         arr[index]=t;
         index++;
      }
      index--;
   return index;
}
void Qsort(int *arr,int start,int end)
{
   int index;
   if (start<end)
   {
      index=part(arr,start,end);
      Qsort(arr,start,index-1);
      Qsort(arr,index+1,end);
   }
}
void Read()
{
   in>>N;
   for(int i=1;i<=N;i++)
   {
      in>>arr;
      sort=arr;
   }
   Qsort(sort,1,N);
}
int find(int n,int *arr,int start,int end)
{
   int pos;
   for(int i=start;i<=end;i++)
      if(arr==n)
      {
         pos=i;
         break;
      }
   return pos;
}
void Reverse(int *arr,int pos)
{
   int t;
   for(int i=1;i<=pos/2;i++)
   {
      t=arr;
      arr=arr[pos-i];
      arr[pos-i]=t;
   }
   for(int i=pos+1;i<=N-(N-pos)/2;i++)
   {
      t=arr;
      arr=arr[N+1-i+pos];
      arr[N+1-i+pos]=t;
   }
   out<<pos<<'\n';
}
bool checkforpos(int sortpos,int arrpos)
{
   int val=false;
   if(arr[arrpos-1]==sort[sortpos-1])
      val=true;
   return val;
}
void Bringforward(int pos)
{
   int posarr=find(sort[pos],arr,1,N);
   if(!checkforpos(pos,posarr))
   {
      Reverse(arr,posarr);
      Reverse(arr,posarr+1);
   }
}
int main()
{
   Read();
   for(int i=1;i<=N;i++)
      Bringforward(i);
   if(arr[1]==sort[N])
      Reverse(arr,N+1);
   return 0;
}