 # 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.   {
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;
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 */
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;
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 is always less than Arr[k+1]-Arr */
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