fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. template<typename T, typename Compare>
  8. class Kopiec //na podstawie hxxp://students.mimuw.edu.pl/~szreder/skrypt.pdf
  9. {
  10.     T* dane;
  11.     int rozm;
  12.     int gora;
  13.     Compare comp;
  14.  
  15.     void heapify_up(int id)
  16.     {
  17.         int rodzic = id / 2;
  18.         if (rodzic && comp(dane[id], dane[rodzic]))
  19.         {
  20.             swap(dane[rodzic], dane[id]);
  21.             heapify_up(rodzic);
  22.         }
  23.     }
  24.  
  25.     void heapify_down(int id)
  26.     {
  27.         int lewy = id * 2, prawy = lewy + 1;
  28.  
  29.         int zmien = id;
  30.         if (lewy <= gora && comp(dane[lewy], dane[zmien]))
  31.         {
  32.             zmien = lewy;
  33.         }
  34.         if (prawy <= gora && comp(dane[prawy], dane[zmien]))
  35.         {
  36.             zmien = prawy;
  37.         }
  38.  
  39.         if (zmien != id)
  40.         {
  41.             swap(dane[zmien], dane[id]);
  42.             heapify_down(zmien);
  43.         }
  44.     }
  45.  
  46.     void alokuj(int nowy_rozmiar)
  47.     {
  48.         T* nowe_dane = new T[nowy_rozmiar + 1];
  49.         for (int i = 1; i <= gora; ++i)
  50.         {
  51.             nowe_dane[i] = dane[i];
  52.         }
  53.         delete[] dane;
  54.         dane = nowe_dane;
  55.         rozm = nowy_rozmiar;
  56.     }
  57.  
  58.     public:
  59.     Kopiec() : dane(new T[2]), rozm(2), gora(0) {}
  60.     ~Kopiec() {delete[] dane;}
  61.  
  62.     void reserve(int i) {alokuj(i + 1);}
  63.  
  64.     T top()
  65.     {
  66.         return dane[1];
  67.     }
  68.  
  69.     void insert(const T& t)
  70.     {
  71.         ++gora;
  72.         if (gora >= rozm)
  73.         {
  74.             alokuj(rozm * 2);
  75.         }
  76.  
  77.         dane[gora] = t;
  78.         heapify_up(gora);
  79.     }
  80.  
  81.     void erase()
  82.     {
  83.         dane[1] = dane[gora--];
  84.         heapify_down(1);
  85.     }
  86.  
  87.     void wypisz()
  88.     {
  89.         for (int i = 1; i <= gora; ++i)
  90.         {
  91.             cout << dane[i] << ' ';
  92.         }
  93.         cout << '\n';
  94.     }
  95.  
  96.     void wczytaj(int ile)
  97.     {
  98.         alokuj(2 * ile);
  99.         gora = ile;
  100.  
  101.         for (int i = 1; i <= ile; ++i)
  102.         {
  103.             cin >> dane[i];
  104.         }
  105.  
  106.         for (int i = ile / 2; i >= 1; --i)
  107.         {
  108.             heapify_down(i);
  109.         }
  110.     }
  111.  
  112.     bool empty()
  113.     {
  114.         return gora == 0;
  115.     }
  116. };
  117.  
  118. struct Spotkanie
  119. {
  120.     int start, end;
  121.     int id;
  122. };
  123.  
  124. struct Przydzial
  125. {
  126.     int id_sali;
  127.     int koniec_obecnego_spotkania;
  128. };
  129.  
  130. int main()
  131. {
  132.     ios_base::sync_with_stdio(false);
  133. 	//cin.tie(nullptr);
  134.  
  135.     int t;
  136.     cin >> t;
  137.     while (t--)
  138.     {
  139.         int ile_sal, ile_spotkan;
  140.         cin >> ile_sal >> ile_spotkan;
  141.         vector<Spotkanie> spotkania(ile_spotkan);
  142.         char dummy;
  143.         int temp;
  144.         for (int i = 0; i < ile_spotkan; ++i)
  145.         {
  146.             cin >> temp >> dummy;
  147.             spotkania[i].start = 60 * temp;
  148.             cin >> temp;
  149.             spotkania[i].start += temp;
  150.             cin >> temp >> dummy;
  151.             spotkania[i].end = 60 * temp;
  152.             cin >> temp;
  153.             spotkania[i].end += temp;
  154.             spotkania[i].id = i + 1;
  155.         }
  156.  
  157.         vector<vector<int>> sale(ile_spotkan);
  158.  
  159.         sort(spotkania.begin(), spotkania.end(), [](const Spotkanie& a, const Spotkanie& b)->bool
  160.         {
  161.            if (a.start != b.start)
  162.            {
  163.                return a.start < b.start;
  164.            }
  165.            return a.end < b.end;
  166.         });
  167.  
  168.         struct comp
  169.         {
  170.             bool operator()(const Przydzial& a, const Przydzial& b)
  171.             {
  172.                 return a.koniec_obecnego_spotkania < b.koniec_obecnego_spotkania;
  173.             };
  174.         };
  175.  
  176.         int licznik_sal = 0;
  177.         Kopiec<Przydzial, comp> kopiec;
  178.         for (const auto& s: spotkania)
  179.         {
  180.             if (kopiec.empty())
  181.             {
  182.                 kopiec.insert(Przydzial{licznik_sal, s.end});
  183.                 sale[licznik_sal++].push_back(s.id);
  184.             }
  185.             else
  186.             {
  187.                 auto k = kopiec.top();
  188.                 if (k.koniec_obecnego_spotkania <= s.start)
  189.                 {
  190.                     sale[k.id_sali].push_back(s.id);
  191.                     kopiec.erase();
  192.                     kopiec.insert(Przydzial{k.id_sali, s.end});
  193.                 }
  194.                 else// if (licznik_sal < sale.size())
  195.                 {
  196.                     sale[licznik_sal].push_back(s.id);
  197.                     kopiec.insert(Przydzial{licznik_sal++, s.end});
  198.                 }
  199.             }
  200.         }
  201.  
  202.         int odbedzie_sie = 0;
  203.  
  204.         sort(sale.begin(), sale.end(), [](const auto& a, const auto& b)->bool {return a.size() > b.size();});
  205.         for (int i = 0; i < min(ile_sal, ile_spotkan); ++i)
  206.         {
  207.             odbedzie_sie += sale[i].size();
  208.         }
  209.  
  210.         cout << odbedzie_sie << '\n';
  211.         for (int i = 0; i < min(ile_sal, ile_spotkan); ++i)
  212.         {
  213.             if (sale[i].empty())
  214.             {
  215.                 break;
  216.             }
  217.  
  218.             for (int j: sale[i])
  219.             {
  220.                 cout << j << ' ';
  221.             }
  222.  
  223.             cout << '\n';
  224.         }
  225.         cout << '\n';
  226.     }
  227. }
  228.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
5
2 3
11:20 12:00
11:30 11:40
11:40 11:55
3 6
17:15 18:30
17:20 19:00
17:15 18:00
16:55 17:55
17:10 18:10
17:00 18:00
2 6
01:00 03:00
03:00 09:00
01:00 05:00
05:00 07:00
07:00 10:00
09:00 10:00
1 3
00:00 02:00
00:01 00:02
00:02 00:03
1 4
00:00 02:00
00:01 00:02
00:02 00:03
02:00 03:00
stdout
copy 
3
2 3 
1 

3
4 
6 
5 

6
1 2 6 
3 4 5 

2
2 3 

3
2 3 4
https://ideone.com/FGmN5G
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!