SHARE
TWEET

Untitled

a guest Oct 12th, 2017 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. #include <fstream>
  6. #include <map>
  7.  
  8. using namespace std;
  9.  
  10. long N, K;
  11.  
  12. typedef class task {
  13.     public:
  14.         long S;
  15.         string name;
  16.         bool operator< (const task& rhs) const {
  17.             return S < rhs.S;
  18.         }
  19. } task;
  20.  
  21. typedef class blockchain {
  22.     public:
  23.         long k;
  24.         vector<task> T;
  25.         blockchain () {}
  26.         blockchain (long _k) : k(_k), T(vector<task> ()) {}
  27.         bool operator< (const blockchain& rhs) const{
  28.             return k < rhs.k;
  29.         }
  30. } blockchain;
  31.  
  32. inline char inc (char in)
  33. {
  34.     return ((in - 65 + K) % 26) + 65;
  35. }
  36.  
  37. int main ()
  38. {
  39.     cin.tie (0);
  40.     ios_base::sync_with_stdio (false);
  41.  
  42.     //ifstream cin("uzduotys.in");
  43.  
  44.     cin >> N >> K;
  45.  
  46.     auto T = vector<task> (N);
  47.     for (long i = 0; i < N; i++)
  48.     {
  49.         cin >> T[i].name >> T[i].S;
  50.     }
  51.  
  52.     sort (T.begin (), T.end());
  53.  
  54.     auto M = map<char, multimap<long, blockchain> > ();
  55.     for (long i = 0; i < K; i++)
  56.     {
  57.         char c = 65 + (i % 26);
  58.         M[c].insert (make_pair (0, blockchain (i)));
  59.     }
  60.  
  61.     for (auto& item : T)
  62.     {
  63.         auto& c = M[item.name[0]];
  64.         auto it = c.begin ();
  65.         if (it != c.end ())
  66.         {
  67.             auto& vec = it->second.T;
  68.             if (vec.empty() || vec[vec.size() - 1].S < item.S)
  69.             {
  70.                 vec.push_back (item);
  71.                 M[inc (item.name[0])].insert (make_pair (vec.size (), it->second));
  72.                
  73.                 c.erase (it);
  74.             }
  75.         }
  76.     }
  77.  
  78.     auto V = vector<blockchain*> (K);
  79.  
  80.     pair<long, long> mini;
  81.     bool found = false;
  82.     for (auto& it : M)
  83.     {
  84.         for (auto& el : it.second)
  85.         {
  86.             V[el.second.k] = &el.second;
  87.             auto tmp = make_pair(el.first, el.second.k);
  88.             if (found == false || mini > tmp)
  89.             {
  90.                 mini = tmp;
  91.                 found = true;
  92.             }
  93.         }
  94.     }
  95.  
  96.     cout << K * mini.first + mini.second << '\n';
  97.     for (long i = 0; i < mini.first; i++)
  98.     {
  99.         for (long j = 0; j < K; j++)
  100.         {
  101.             cout << V[j]->T[i].name << '\n';
  102.         }
  103.     }
  104.     for (long i = 0; i < mini.second; i++)
  105.     {
  106.         cout << V[i]->T[mini.first].name << '\n';
  107.     }
  108.     //cin.close ();
  109. }
RAW Paste Data
Top