Guest User

CAMC - solution

a guest
Nov 11th, 2019
182
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<pair<long long int,long long int > >vec;
  5. vector<long long int> mark(100009);
  6. vector<long long int >sample(100009);
  7. unordered_map<long long int ,long long int >org;
  8.  
  9.  
  10.  
  11.  
  12.  /* We would first mark all the vector elements with their respective colors and as for every M elements they are unique
  13.     so it will just repeat as 1,2,3....m,1,2,3... */
  14.  
  15.   void init(long long int  N, long long int  M)
  16.   {
  17.         long long int  it=1;
  18.         for(long long int  i=0;i<N;i++)
  19.         {
  20.             mark[i]=it;
  21.             it++;
  22.             if(it>M)
  23.             {
  24.                it=1;
  25.             }}}
  26.  
  27.  /* Now I will pair their color with the actual numbers, mark vector can be excluded and this process can be dN in a
  28.     single loop for memory efficiency but I have dN this for simplicity */
  29.  
  30.   void filling(long long int N)
  31.   {
  32.       for(long long int  i=0;i<N;i++)
  33.         {
  34.             vec.push_back(make_pair(sample[i],mark[i]));
  35.         }
  36.   }
  37.  
  38.   /*Initialsing first k elements in the map to cover cases with k or more than k elements with same value (answer will be 0 in that case)*/
  39.  
  40.   void gut(long long int  M)
  41.   {
  42.  
  43.        for(long long int  i=0;i<M;i++)
  44.             org[vec[i].second]++;
  45.   }
  46.  
  47.  
  48.   void solve(long long int  N, long long int  M)
  49.   {
  50.        long long int  final_answer=INT_MAX;
  51.        long long int  forv=0; /* first iterator*/
  52.        long long int  backw=M-1; /* second iterator*/
  53.        long long int  height=0; /* calculating variable*/
  54.        gut(M);
  55.        if(org.size()==M)
  56.        {
  57.            height=vec[backw].first-vec[forv].first;
  58.            final_answer = min(height,final_answer);
  59.        }
  60.        while(1)
  61.        {
  62.            if(org.size()==M)
  63.            {
  64.                long long int  height = vec[backw].first-vec[forv].first; /* check for minimum value */
  65.                final_answer=min(final_answer,height);
  66.                org[vec[forv].second]--; /* Now we will increase the first iterator until we get to the point where the map size again becomes<M and that point will be the minimum value */
  67.                if(org[vec[forv].second]==0) org.erase(vec[forv].second); /* once we have one colour completed, we would delete this from the map*/
  68.                forv++;
  69.            }
  70.            else
  71.            {
  72.                backw++; /* we increase the second iterator till we get the map size == M */
  73.                if(backw>vec.size()-1)
  74.                   break;
  75.                org[vec[backw].second]++;}} /* also we will keep adding the colour */
  76.         cout << final_answer << endl;
  77.         final_answer=INT_MAX;
  78.         org.clear();
  79.         sample.clear();
  80.         mark.clear();
  81.         vec.clear();
  82.   }
  83.   int main()
  84.   {
  85.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  86.     long long int  test;
  87.     cin >> test;
  88.     while(test--)
  89.     {
  90.         long long int  N,M;
  91.         cin >> N >> M;
  92.         for(long long int  i=0;i<N;i++)
  93.         {
  94.             cin >> sample[i];
  95.         }
  96.         init(N,M);
  97.         filling(N);
  98.         sort(vec.begin(),vec.end()); /* sorting to get the the difference easily as  Arr[k]-Arr[0] is always less than Arr[k+1]-Arr[0] */
  99.         vector<long long int >point;
  100.         for(long long int  i=0;i<N;i++)
  101.             point.push_back(vec[i].second);
  102.  
  103.         solve(N,M);
  104.     }
  105.     return 0;
  106. }
RAW Paste Data