Re: 120 Still WA. If you get AC, please try this input.
Posted: Wed Feb 11, 2009 10:15 am
Accepted
Code: Select all
8 4 6 7 5 2
1 4 2 5 3 4 5 0
1 2 3 5 4
2 1 2 3 0
7 3 5 4 8 9 10 1 13
3 2 8 5 8 6 0
2
0
33 21 45
2 0
33 55
0
1
0
2 1
1 0
1 2
0
56 12 48
1 2 0
75 2 1 44 53 84 21 46 82 43 99 49 89 7 9
5 1 13 2 11 3 6 4 10 5 14 6 7 10 8 12 9 11 14 12 14 0
1 2 3 6 7 8 4 5
3 1 4 6 0
1 3 19 4 95 62 42 43 13 2
6 1 6 2 4 3 4 6 5 9 6 8 9 0
1 2 3 4 5 6 7 8 9 10 11 12 14 13 15 16 17 18 19 20
8 7 8 9 0
Code: Select all
1 2 3 5 4
Code: Select all
1 2 3 5 4
2 1 2 3 0
Code: Select all
1 5 4 3 1
2 flip(2) 3 flip(1) 1 flip(2) 2 flip(3) 2
3 ------> 2 ------> 2 ------> 1 ------> 3
5 1 3 4 4
4 4 5 5 5
Code: Select all
I submit the same code in the next day
and it is accepted-.-
Code: Select all
#include <cstdio>
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <utility>
#define pa pair<int,int>
using namespace std;
bool com(const pa a,const pa b)
{
return a.first<b.first;
}
vector<pa> getNumber(string st)
{
vector <pa> vec;
int num;
int ind=0;
char str[500];
strcpy(str,st.c_str());
char *ptr;
ptr=strtok(str," ");
while(ptr!=NULL)
{
sscanf(ptr,"%d",&num);
vec.push_back(pa(num,ind++));
ptr=strtok(NULL," ");
}
return vec;
}
void _swap(pa &a,pa &b)
{
pa tmp;
tmp=a;
a=b;
b=tmp;
}
int main()
{
string st;
vector <pa> vec;
vector <pa> cvec;
int length;
bool flag=false;
while(getline(cin,st))
{
vec.clear();
cvec.clear();
vec = getNumber(st);
cvec = vec;
sort(cvec.begin(),cvec.end(),com);
length=vec.size();
flag=false;
for(int i=length-1;i>0;i--)
{
if(vec[0].second == cvec[i].second)
{
for(int k=0,l=i;k<l;k++,l--)
_swap(vec[k],vec[l]);
cout<<length-i<<" ";
}
else{
for(int j=i-1;j>0;j--)
{
if(cvec[i].second==vec[j].second)
{
for(int k=0,l=j;k<l;k++,l--)
_swap(vec[k],vec[l]);
cout<<length-j<<" ";
for(int k=0,l=i;k<l;k++,l--)
_swap(vec[k],vec[l]);
cout<<length-i<<" ";
}
}
}
}
cout<<"0"<<endl;
}
return 0;
}
My friend,raj wrote:1 2 3 5 4
2 1 2 3 0
I DIDNT UNDERSTAND THIS CASE ............
PLS ANYONE MAKE ME UNDERSTOOD ELABORATELY ..??????
Code: Select all
5 1 2 3 4
Code: Select all
5 1 2 3 4
1 2 0
Code: Select all
#include <vector>
#include <iterator>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <sstream>
using namespace std;
int main()
{
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
string s;
while(getline(cin, s))
{
istringstream ss(s);
vector<int> pancakes, flips;
int p;
while(ss >> p)
pancakes.push_back(p);
printf("%d", pancakes[0]);
for(int i=1; i<pancakes.size(); i++)
printf(" %d", pancakes[i]);
printf("\n");
reverse(pancakes.begin(), pancakes.end());
vector<int> originals(pancakes);
int sorted = 0;
while(sorted < pancakes.size())
{
auto flipIt = max_element(pancakes.begin()+sorted, pancakes.end());
int flipInd = distance(pancakes.begin()+sorted, flipIt);
if(flipInd != 0)
{
if(flipIt != pancakes.end()-1)
{
flips.push_back(flipInd+sorted+1);
reverse(flipIt, pancakes.end());
}
flips.push_back(sorted+1);
reverse(pancakes.begin()+sorted, pancakes.end());
}
sorted++;
}
// printf("checking\n");
// for(auto f:flips)
// reverse(originals.begin()+(f-1), originals.end());
// reverse(originals.begin(), originals.end());
// if(is_sorted(originals.begin(), originals.end()))
// {
// printf(" Yay!\n");
// }
// else
// printf(" Fuck!\n");
for(auto f:flips)
printf("%d ", f);
printf("0\n");
}
}