482 - Permutation Arrays

[lbv]

i m still getting WA. please help.

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]

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]

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.

[Munchor]

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]

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 read(in) freopen("in.txt","r",stdin);
#define write(out) freopen("out.txt","w",stdout);
using namespace std;

string s1;
int arr[100000];
int main()
{
    //read(in);
    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]

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.

[Kenpachi24]

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 

[brianfry713]

The outputs of two consecutive cases will be separated by a blank line. Don't print an extra blank line at the end.

[Kenpachi24]

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

What do you recommend?

[uDebug]

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.

[uDebug]

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?

[uDebug]

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.

[Kenpachi24]

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]

AC

Well done! I'm glad you figured it out!

[jddantes]

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;
}