Advertisement
daksh_ddt

Help Cupid Wrong Answer

Nov 14th, 2014
274
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.93 KB | None | 0 0
  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <queue>
  6. #include <deque>
  7. #include <stack>
  8. #include <bitset>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <numeric>
  12. #include <utility>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <iomanip>
  16. #include <cstdio>
  17. #include <cmath>
  18. #include <cstdlib>
  19. #include <cstring>
  20. #include <queue>
  21. #include <ctime>
  22. #include <cassert>
  23. #include <climits>
  24. #include <limits>
  25. using namespace std;
  26.  
  27. typedef vector <int> vi;
  28. typedef pair< int ,int > ii;
  29.  
  30. #define S(a) scanf("%d",&(a))
  31. #define P(a) printf("%d",(a))
  32. #define PS printf(" ")
  33. #define NL printf("\n")
  34. #define SL(a) scanf("%lld",&(a))
  35. #define PL(a) printf("%lld",(a))
  36. #define LL long long int
  37. #define FOR(I,A,B) for(int I= (A); I<(B); ++I)
  38. #define all(c) c.begin(), c.end()
  39. #define stop system("pause")
  40. #define pb push_back
  41. #define mp make_pair
  42. #define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
  43. #define INDEX(arr,ind)          (lower_bound(all(arr),ind)-arr.begin())
  44. #define ff first
  45. #define ss second
  46.  
  47. #define imax numeric_limits<int>::max()
  48. #define imin numeric_limits<int>::min()
  49. #define lmax numeric_limits<ll>::max()
  50. #define lmin numeric_limits<ll>::min()
  51.  
  52. int ar[1010];
  53.  
  54. struct node{
  55.     int x;
  56.     int y;
  57.     int val;
  58. };
  59.  
  60. vector<node> dist;
  61.  
  62. vector<node> store[25];
  63.  
  64. map<int,int> mark;
  65.  
  66. void init(){
  67.     mark.clear();
  68.     dist.clear();
  69.     FOR(i,0,25)
  70.         store[i].clear();
  71.      
  72. }
  73.  
  74. void do_sort(){                 //linear-time sorting
  75.     int sz = dist.size();
  76.     FOR(i,0,sz){
  77.         store[dist[i].val].pb(dist[i]);
  78.     }
  79.    
  80.     dist.clear();
  81.     FOR(i,0,25){
  82.         int sz = store[i].size();
  83.         FOR(j,0,sz){
  84.             dist.pb(store[i][j]);
  85.         }
  86.     }    
  87.    
  88. }
  89.  
  90. int main(){
  91.     int n;
  92.     int flag = 0;
  93.     while(S(n)==1){
  94.         if(flag)
  95.             NL;
  96.         init();
  97.         FOR(i,0,n){
  98.             S(ar[i]);
  99.             mark[ar[i]]++;      //mark stores the frequency of each element
  100.         }
  101.         FOR(i,0,n){
  102.             FOR(j,i+1,n){
  103.                 int value =  min(abs(ar[i]-ar[j]),24-abs(ar[i]-ar[j]));
  104.                 node temp;
  105.                 temp.x = ar[i];
  106.                 temp.y = ar[j];
  107.                 temp.val = value;
  108.                 dist.pb(temp);
  109.             }
  110.         }
  111.        
  112.         do_sort();  //sort the distances
  113.         int ct = 0;
  114.         int ans = 0;
  115.         int i = 0;
  116.        
  117.         while(ct<n/2){  //select N/2 distances
  118.                    
  119.             if(mark[dist[i].x]==0 || mark[dist[i].y]==0 || (dist[i].x == dist[i].y && mark[dist[i].x]<=1) ){
  120.                 i++;
  121.             }
  122.             else{
  123.                 ans +=dist[i].val;
  124.                 mark[dist[i].x]--;
  125.                 mark[dist[i].y]--;
  126.                 ct++;
  127.                 i++;
  128.             }
  129.         }
  130.         P(ans);    
  131.     }
  132.     return 0;
  133. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement