jakaria_hossain

codeforces - zero reminder array

Jun 28th, 2020
1,359
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. #define ll long long
  5. #define fast()(ios_base::sync_with_stdio(0),cin.tie(NULL));
  6. #define pi pair<int , int>
  7. #define mp make_pair
  8. #define f first
  9. #define s second
  10.  
  11. int main()
  12. {
  13.     ll t;
  14.     cin>>t;
  15.     while(t--)
  16.     {
  17.         ll n,k,mx=0;
  18.         cin>>n>>k;
  19.         map<ll,ll>mp;
  20.         queue<ll>q;
  21.         ll ara[n+1];
  22.         for(ll i=0; i<n; i++)
  23.         {
  24.             cin>>ara[i];
  25.  
  26.         }
  27.         sort(ara,ara+n);
  28.         for(ll i=0; i<n; i++)
  29.         {
  30.             ll x=k-(ara[i]%k);
  31.             if(x==k)continue;
  32.             else
  33.             {
  34.                 mp[x]++;
  35.                 q.push(x);
  36.             }
  37.         }
  38.         while(!q.empty())
  39.         {
  40.             ll x= q.front();
  41.             if(mp[x]>1)
  42.             {
  43.                 mp[x]--;
  44.                 ll y=mp[x]*k+x;
  45.                 mx=max(mx,y);
  46.                 mp[y]++;
  47.                 q.push(y);
  48.                 q.pop();
  49.             }
  50.             else
  51.             {
  52.                 mx=max(mx,x);
  53.                 q.pop();
  54.             }
  55.         }
  56.         if(mx>0)mx++;
  57.         cout<<mx<<endl;
  58.     }
  59.  
  60. }
RAW Paste Data