UVa : 482 (Permutation Arrays)


Title : Permutation Arrays

Link : http://uva.onlinejudge.org/external/4/482.html

Tricky Lines :

  1. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
    The outputs of two consecutive cases will be separated by a blank line.

Analysis :

  1. first line gives you the index numbers and second line the values
  2. as there is no indication number of input numbers, may be there is no other way to take the input as string
  3. after taking input as string, u need to parse the index value as integer
  4. to avoid precision problem, take the second lines values as string
  5. just sort it, based on index number and print

Runtime : 0.024s

Solution :

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#define INT_MAX 2147483647
#define INT_MIN -2147483648
#define pi acos(-1.0)
#define N 1000000
#define LL long long
using namespace std;

struct array {
    int in;
    string num;
} a [10000];

bool cmp (array x, array y)
{
    if ( x.in < y.in ) return true;
    return false;
}

int main ()
{
    int testCase;
    scanf ("%d", &testCase);
    getchar ();

    bool blank = false;

    while ( testCase-- ) {
        char input [100000];
        gets (input);
        gets (input);

        char *pch = strtok (input, " ");
        int index = 0;

        while ( pch != NULL ) {
            a [index].in = atoi (pch);
            pch = strtok (NULL, " ");
            index++;
        }

        gets (input);

        pch = strtok (input, " ");
        index = 0;

        while ( pch != NULL ) {
            a [index].num = pch;
            pch = strtok (NULL, " ");
            index++;
        }

        sort (a, a + index, cmp);

        if ( blank ) printf ("\n");
        blank = true;

        for ( int i = 0; i < index; i++ )
            cout << a [i].num << endl;
    }

	return 0;
}

// @END_OF_SOURCE_CODE

3 thoughts on “UVa : 482 (Permutation Arrays)

  1. Another smaller solution (on your idea only) using STL could be:

    #include
    #include
    #include
    #include
    #include
    #include
    #include
    using namespace std;
    int main (int argc, const char * argv[])
    {
    int t, count=0;
    string line1, line2;
    int index;
    string value;
    vector<pair > store;
    cin>>t;
    getchar();
    while (t–) {
    getchar();
    count++;
    getline(cin, line1);
    getline(cin, line2);
    stringstream ss1(line1), ss2(line2);
    while (ss1>>index) {
    ss2>>value;
    store.push_back(pair(index, value));
    }
    sort(store.begin(), store.end());
    if (count>1) {
    cout<<endl;
    }
    for (int i=0; i<store.size(); i++) {
    cout<<store[i].second<<endl;
    }

    store.clear();
    }
    return 0;
    }

  2. what is wrong with it?
    #include
    #include
    #include
    int main()
    {
    int i,j,d,l,n,q,k,u,p;
    char str2[1000][1000],ch;
    int ara[150000];
    scanf(“%d”,&n);
    printf(“\n”);
    for(p=0;p0)if(ch==’\n’){
    ara[i]=k;
    k=0;
    i++;
    break;
    }
    if((int)ch!=32&&(ch)!=10)k=((int)ch-48)+k*10;

    if(ch==’ ‘){
    ara[i]=k;
    k=0;
    i++;
    }
    u++;
    }
    for(l=0;l<i;l++){
    scanf("%s",str2[ara[l]]);

    }
    for(l=1;l<=i;l++){
    printf("%s\n",str2[l]);
    }
    printf("\n");
    }
    return 0;
    }

  3. // Running time : 0.000 secs
    // Complexity : O(n)

    #include
    #include
    #include

    using namespace std ;

    int main()
    {
    vector v1 ;
    vector v2 ;

    string s, t, str;

    int test , ind ;
    cin>>test ;

    getchar();

    while(test–)
    {

    getchar();
    getline(cin,s);
    stringstream ss(s);
    while(ss>>ind) v1.push_back(ind);
    getline(cin,str);
    stringstream sst(str);
    while(sst>>t) v2.push_back(t);

    vectorv3( v1.size() + 1 ) ;

    for(int i=0;i<v1.size() ; i++ ) //hash it
    {
    v3[v1[i]] = i ;
    }

    for(int i=1 ; i<=v1.size() ; i++ )
    {
    cout<<v2[v3[i]]<<endl ;
    }
    v1.clear() ;
    v2.clear() ;
    v3.clear() ;
    if(test)
    printf("\n") ;
    }
    return 0 ;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s