## 482 - Permutation Arrays

Moderator: Board moderators

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

### Re: 482 Permutation Arrays

Since this problem doesn't have an explicit specification for how large n could be, and the size in characters of each line, it's risky to make assumptions and declare fixed-size arrays to hold the data. However, take the time to read the previous comments from this forum thread. The post made by bill8124 on Jul 27, 2012, for example, has some useful information.

Alternatively, you could write a program that doesn't make any assumptions in the size of the input (using C++ structs like strings, vectors, etc.)

Munchor
New poster
Posts: 19
Joined: Sun Mar 03, 2013 4:03 pm

### Re: 482 Permutation Arrays

brianfry713 wrote:It looks like you misunderstood the problem. Don't sort an array of doubles, just keep them as strings. Permute the strings according to the index array.
brianfry713, take a look at this example case:

Code: Select all

``````1

3 1 2
32.0 54.7 -2
``````
I sort the values and I get "-2", "32.0", "54.7". Then the "3 1 2" means - "first print the third (54.7), then the first (-2) then the second (32.0). I definitely have to sort them, it's not just printing out the third, the first and the second from the order of input.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 482 Permutation Arrays

That's not what the problem is asking. Don't sort the doubles, keep them as strings
"32.0" should be the third element in the new array.
"54.7" should be the first element in the new array.
"-2" should be the second element in the new array.
Check input and AC output for thousands of problems on uDebug!

Munchor
New poster
Posts: 19
Joined: Sun Mar 03, 2013 4:03 pm

### Re: 482 Permutation Arrays

brianfry713 wrote:That's not what the problem is asking. Don't sort the doubles, keep them as strings
"32.0" should be the third element in the new array.
"54.7" should be the first element in the new array.
"-2" should be the second element in the new array.
Thank you, I completely misunderstood the problem!

hello
New poster
Posts: 25
Joined: Sun Mar 10, 2013 7:29 pm

### Re: 482 Permutation Arrays

Got RE...

Code: Select all

``````    //bismillahhirrahmanirrahim
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#define zero(arr) memset(arr,0,sizeof(arr));
#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,m,n,k) for(int i=m;i<n;i=i+k)

#define VI vector<int>
#define VVI vector< VI >
#define VIit VI::iterator

#define pb(a) push_back(a)
#define SI(a) scanf("%d",&a)
#define SU(a) scanf("%u",&a)
#define SHD(a) scanf("%hd",&a)
#define SHU(a) scanf("%hu",&a)
#define SLLD(a) scanf("%lld",&a)
#define SLLU(a) scanf("%llu",&a)
#define SF(a) scanf("%f",&a)
#define SLF(a) scanf("%lf",&a)
#define SC(a) scanf("%c",&a)
#define SS(a) scanf("%s",a)
#define swp(type, a, b) {type x=a; a=b; b=x;}
#define write(out) freopen("out.txt","w",stdout);
using namespace std;

string s1;
int arr[100000];
int main()
{
int cases,flag=0;
SI(cases);
getchar();
getchar();
while(cases--){

getline(cin,s1);
s1+="-1";
istringstream iss(s1);
int index=1;
while(1){
iss >> arr[index++];
if(arr[index-1]==-1)break;
}
string s;
vector<string> V(index-1);
FOR(i,1,index-1,1){
cin>>s;
V[arr[i]]=s;
}
getchar();
if(flag)puts("");
flag=1;
FOR(i,1,index-1,1)cout<<V[i]<<endl;
}
return 0;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 482 Permutation Arrays

Don't use a single getchar() and count on it to be a newline, that won't work if there is trailing whitespace on a line.
Check input and AC output for thousands of problems on uDebug!

Kenpachi24
New poster
Posts: 20
Joined: Wed Oct 30, 2013 7:06 pm

### Re: 482 Permutation Arrays

I have WA. I think that's by output of the blank lines; accept suggestions (I know should use any data structure, but I think that does not affect WA)

Code: Select all

``````remove by AC
``````
Last edited by Kenpachi24 on Sat Dec 14, 2013 4:04 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 482 Permutation Arrays

The outputs of two consecutive cases will be separated by a blank line. Don't print an extra blank line at the end.
Check input and AC output for thousands of problems on uDebug!

Kenpachi24
New poster
Posts: 20
Joined: Wed Oct 30, 2013 7:06 pm

### Re: 482 Permutation Arrays

I delete the line "System.out.println()" and even I Have WA

What do you recommend?

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 482 Permutation Arrays

brianfry713 shared this information with me and I found it incredibly useful to solve this problem.
My AC code on 482 assumes a line is less than 100,000 characters and there are up to 10,000 numbers on a line.
Check input and AC output for over 7,500 problems on uDebug!

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 482 Permutation Arrays

Kenpachi24 wrote:I delete the line "System.out.println()" and even I Have WA

What do you recommend?
I just now ran your program and this is the output I see

Code: Select all

``````54.7
-2.0
32.0``````
Looking at your code and at this line

Code: Select all

``double arreglo[]=new double[1000000];``
This is probably what's causing things to trip up.

Look at the sample input / output more carefully. There's both

Code: Select all

``32.0``

and

Code: Select all

``-2``
Your code prints the extra ".0"after "-2".

Does this suggest taking another approach to the problem?
Last edited by uDebug on Thu Dec 12, 2013 9:19 am, edited 1 time in total.
Check input and AC output for over 7,500 problems on uDebug!

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 482 Permutation Arrays

Also, for anyone else wondering about or having formatting issues. My AC code for the following input

Code: Select all

``````3

3 1 2
32.0 54.7 -2

3 2 1
2 5 6.0

1
7.0``````
gives the following output

Code: Select all

``````54.7
-2
32.0

6.0
5
2

7.0``````

There is a blank line after every set of output. However, as mentioned several times before, there is no blank line after the last set of output.
Check input and AC output for over 7,500 problems on uDebug!

Kenpachi24
New poster
Posts: 20
Joined: Wed Oct 30, 2013 7:06 pm

### Re: 482 Permutation Arrays

AC

thank you very much ( brianfry713 - v1n1t) by the observations and clarifications; definitely I should use String; and the problem of the blank line I was misinterpreting

again, thank you very much

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 482 Permutation Arrays

Kenpachi24 wrote: AC
Well done! I'm glad you figured it out!
Check input and AC output for over 7,500 problems on uDebug!

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

### Re: 482 Permutation Arrays

What's wrong with mine?

Code: Select all

``````
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main()
{
int cases;
char x;
scanf("%d%c",&cases,&x);
int e;
for(e=0; e<cases; e++)
{
char buff[50];
fgets(buff, 50, stdin);

char * word_list[100500];
memset(word_list,0, sizeof(word_list));

//printf("Input indices:\n");
char scan_index[100500];
fgets(scan_index, 100500, stdin);

char scan_values[100500];
fgets(scan_values,100500, stdin);
scan_values[strlen(scan_values) - 1] = 0;

int index;

FILE *stream_index;
FILE *stream_values;
stream_index = fmemopen(scan_index, strlen(scan_index), "r");
stream_values = fmemopen(scan_values, strlen(scan_values), "r");

while(fscanf(stream_index, "%d", &index)!=EOF)
{
//  printf("Index is %d\n", index);

char word[1000];
fscanf(stream_values, "%s", word);
// printf("Word is %s\n", word);

word_list[index] =(char *)malloc(sizeof(word));
strcpy(word_list[index], word);

// printf("Word in list is %s\n",word_list[index]);

//getchar();
}

fclose(stream_index);
fclose(stream_values);

int i;
for(i=1; word_list[i]; i++)
{
printf("%s\n",word_list[i]);
free(word_list[i]);
}
printf("\n");

}

return 0;
}

``````