## 482 - Permutation Arrays

Moderator: Board moderators

andy0518
New poster
Posts: 2
Joined: Wed Aug 20, 2008 5:21 pm

### Re: 482 Permutation Arrays

I think my array is big enough, but it is still Run Time Error.
Can anyone help me?
Thank you

Code: Select all

``````#include<iostream>
#include<algorithm>
#define MAX 600000
using namespace std;
int main()
{
int t,order[MAX];
char text[MAX];
char *token;
char item[MAX/2][100];
cin.getline(text,MAX);
t = atoi(text);
while(t--)
{
cin.getline(text,MAX);
cin.getline(text,MAX);
token = strtok(text," ");
for(int i=0; token != NULL; i++)
{
order[i] = atoi(token);
token = strtok(NULL," ");
}
cin.getline(text,MAX);
token = strtok(text," ");
int i;
for(i=0; token != NULL; i++)
{
strcpy(item[order[i]-1], token);
token = strtok(NULL," ");
}
for(int j=0; j<i; j++)
printf("%s\n",item[j]);
if(t != 0)
printf("\n");
}
return 0;
}
``````

tanvir_cse
New poster
Posts: 9
Joined: Wed Jul 09, 2008 10:12 pm

### Re: 482 Permutation Arrays

hi, u cant declare an array of size 600,000. array size can be 90000, or some greater than this. I got RTE just for declaring #define SIZE 100000

tanvir_cse
New poster
Posts: 9
Joined: Wed Jul 09, 2008 10:12 pm

### Re: 482 What A Trick

My Algo...
1.Take test case
2.declare an int array[80000]. Then take input like this for first line i,e 3 1 2 )
ch='*'; i=0;
while(ch!='\n')
{
scanf("%d",&array[i++]);
scanf("%c",&ch);
}

3.then take second line of input using 2D array of characters by str[8000][80];
4. Do other process as u need for ur problem.
5. When u r submitting the code just make : 1.int array[100000] and str[20000][50]
Dont try to Run ur code after making change.It will not run for VC++ users
Thats the trick i used to get AC.

qwerty
New poster
Posts: 21
Joined: Sun Feb 08, 2009 5:26 pm
Location: Mumbai,India

### Re: 482 Permutation Arrays

Code: Select all

``````acc
``````
Last edited by qwerty on Thu Feb 25, 2010 12:34 am, edited 1 time in total.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 482 Permutation Arrays

I changed my code again and again but again and again wA!!!! someone plz help me.... At least prove me wrong..

Code: Select all

``removed``
Last edited by Obaida on Sat Mar 14, 2009 11:03 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 482 Permutation Arrays

Some one please give me test case.
try_try_try_try_&&&_try@try.com
This may be the address of success.

Moshiur Rahman
New poster
Posts: 13
Joined: Mon Sep 08, 2008 6:57 pm

### Re: 482 Permutation Arrays

I think you have to change your method of "input taking" for second input line.
you can use the value of i to take the second line. Note that, you will be given exactly i floating point numbers.
So, you don't need to worry about the white spaces. You get the value of i from the while loop that takes the first input line.
Just replace the for() loop with this one:

Code: Select all

``````for(k = 0; k < i; ++k)
{
scanf("%s",st[num[k]-1]);
}
``````
So, you can get rid of the len[] array too.
Never think too hard, let ideas come to you...

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 482 Permutation Arrays

Thanks for giving me a good lesson.
Thank you very much.
try_try_try_try_&&&_try@try.com
This may be the address of success.

toru
New poster
Posts: 17
Joined: Tue Dec 30, 2008 10:38 am

### 482 Permutation Arrays (HELP!!!!!!!!!!!!!!!!!)

HI, hope every1 is good here, but i m really sick of this problem, i don't know why i m repeatedly getting CE for this one, the judge says:...........

"
code.o: In function `main':
code.cpp:(.text+0xab): warning: the `gets' function is dangerous and should not be used.
code.o: In function `__static_initialization_and_destruction_0(int, int)':
code.cpp:(.text+0x19): relocation truncated to fit: R_X86_64_32 against `.bss'
code.o: In function `__tcf_0':
code.cpp:(.text+0x51): relocation truncated to fit: R_X86_64_32 against `.bss'
collect2: ld returned 1 exit status

"
i completely don't understand, plzzz anyone help me to get rid of it......................
TORU.

Code: Select all

``````#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
using namespace std;

#define MAX  100000

struct List
{
char fir[50000];
char sec[50000];
}list[MAX];

int sort_function( const void *a, const void *b)
{
char *s, *t;

s = ((struct List*)a)->fir;
t = ((struct List*)b)->fir;
return strcmp(s,t);
}

int main()
{
char buf[MAX], *ch;
long kase, N, i;

cin>>kase;
while(kase--)
{
printf("\n");
N=0;

gets(buf);
ch=strtok(buf, " ");
while(ch)
{
strcpy(list[N].fir, ch);
N++;
ch=strtok(NULL, " ");
}

N=0;
gets(buf);
ch=strtok(buf, " ");
while(ch)
{
strcpy(list[N].sec, ch);
N++;
ch=strtok(NULL, " ");
}

qsort( (void *)list, N, sizeof(list[0]), sort_function);

for(i=0; i<N; i++)
cout<<list[i].sec<<endl;

if(kase != 0)
printf("\n");
}
return 0;
}

``````

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 482 Permutation Arrays

Your program allocates too much memory, almost 9Gb.
And gcc limits statically-allocated memory to only about 2-4Gb even in 64-bit mode. (And in 32-bit mode which judge uses, it should be even a lot less)

toru
New poster
Posts: 17
Joined: Tue Dec 30, 2008 10:38 am

### Re: 482 Permutation Arrays

ok mf,
almost 9Gb.
oh my god, dats too much, i better shorten up my array and then try, thankz..
toru.

toru
New poster
Posts: 17
Joined: Tue Dec 30, 2008 10:38 am

### Re: 482 Permutation Arrays

Got rid of CE, but now Run time error every time, i guess i just followed a simple algo.. but then why ?????????
what can i do??????? PLZZZZZ HELP..............

ngockhanhdao
New poster
Posts: 1
Joined: Sat Sep 18, 2010 10:46 pm

### Re: 482 Permutation Arrays

Can anybody help me explain why run-time error ? I tested the inputs and outputs and they're all correct.

Code: Select all

``````#include <iostream>
using namespace std;

int main()
{

int listIndex[10]; int length = 0;
char listFloat[10][10];
char listPermuted[10][10] = {NULL};

int n;
cin >> n;  // get #of inputs
cin.ignore(256, '\n');
cout << endl;

for (int z = 0; z < n; z++)
{
// get the list of indexes
do
{
cin >> listIndex[length];
length++;
}while (cin.get() != '\n');

// get the list of float numbers
int i = 0;
while (i < length)
{
cin >> listFloat[i];
i++;
}

// now permuted array
int j;
for (i = 0; i < length; i++)
{
j = listIndex[i] - 1;
strcpy(listPermuted[j], listFloat[i]);
}

for (i = 0; i < length; i++)
{
cout << listPermuted[i] << endl;
}

length = 0;
cout << endl;

}
cout << endl;

system("pause");
return 0;
}

``````

bachachele
New poster
Posts: 1
Joined: Sat Nov 13, 2010 8:56 am

### Re: 482 Permutation Arrays

do not print a new line after the last output...,gave me a lot of pain before getting AC.....

nhrahi
New poster
Posts: 6
Joined: Tue Aug 25, 2009 7:38 pm

### Re: 482 Permutation Arrays

``````