problem link – http://www.spoj.com/problems/QUE1/
Vector of pairs is used to store the height and count of taller person standing before.
This problem can be solved by sorting the vector based on height.
Assign the final position for each person i in the answer array by moving them C empty positions from the index 0 where
C = count of taller person who are standing before person i
Detailed explanation is in the comments of the code below.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <vector> | |
| #include <list> | |
| #include <map> | |
| #include <set> | |
| #include <deque> | |
| #include <queue> | |
| #include <stack> | |
| #include <bitset> | |
| #include <algorithm> | |
| #include <functional> | |
| #include <numeric> | |
| #include <utility> | |
| #include <sstream> | |
| #include <iostream> | |
| #include <iomanip> | |
| #include <cstdio> | |
| #include <cmath> | |
| #include <cstdlib> | |
| #include <ctime> | |
| #include <cstring> | |
| #include <climits> | |
| #include <stdlib.h> | |
| #include <stdio.h> | |
| using namespace std; | |
| #define REP(i,n) for(int i=0; i<n; i++) | |
| #define FOR(i,st,end) for(int i=st;i<end;i++) | |
| #define db(x) cout << (#x) << " = " << x << endl; | |
| #define mp make_pair | |
| #define pb push_back | |
| #define MAX 10000005 | |
| typedef long long int ll; | |
| int ans[1005]; | |
| int main(){ | |
| int t,n; | |
| vector<pair<int,int> >arr; | |
| scanf("%d",&t); | |
| while(t--){ | |
| scanf("%d",&n); | |
| arr.resize(n); | |
| memset(ans,0,sizeof ans); | |
| //height | |
| REP(i,n){ | |
| scanf("%d",&arr[i].first); | |
| } | |
| //count of ppl whose height is greater than the person at position i | |
| REP(i,n){ | |
| scanf("%d",&arr[i].second); | |
| } | |
| //sort the vector of pairs based on the height | |
| sort(arr.begin(),arr.end()); | |
| int greaterCount=0; | |
| REP(i,n){ | |
| //greaterCount = count of ppl whose height is greater than the person at position i | |
| greaterCount=arr[i].second; | |
| REP(j,n){ | |
| //if there is no person whose height is greater than the height of current person (positioned at i) is found | |
| //and if position j in ans array is not filled yet,then assign that person to position j | |
| if(greaterCount==0&&ans[j]==0){ | |
| ans[j]=arr[i].first; | |
| break; | |
| } | |
| //decrement the greaterCount eachtime when an unfilled answer position is found | |
| //this implicitly means: decrement the greaterCount eachtime when a person with height greater than the current person i is found | |
| if(ans[j]==0) | |
| greaterCount--; | |
| } | |
| } | |
| REP(i,n){ | |
| printf("%d ",ans[i]); | |
| } | |
| printf("\n"); | |
| } | |
| } |
coding hangover 