#include <iostream> #include <vector> #include <algorithm> #include <stdint.h> #include <set> #include <tuple> using namespace std; struct piekarnik { public: int index; int czas_piecz; int64_t suma_czekania; piekarnik(){} piekarnik (int czas, int ind) : index(ind), czas_piecz(czas), suma_czekania(0){} static bool cmp_index (const piekarnik & a, const piekarnik & b) {return a.index < b.index;} static bool cmp_czas (const piekarnik & a, const piekarnik & b) {return a.czas_piecz < b.czas_piecz;} }; template <class T> vector<T> wczytaj_dane(int ile) { vector<T> dane(ile, 0); for (int ii=0; ii<ile; ii++) { T dana_ii; cin>>dana_ii; dane[ii] = dana_ii; } return dane; } vector<piekarnik> wczytaj_piek(int ile) { vector<piekarnik> piek(ile); for (int ii=0; ii<ile; ii++) { int dana_ii; cin>>dana_ii; piek[ii] = piekarnik(dana_ii, ii); } return piek; } bool cmp_greater (const int i, const int j) { return (i>j); } int64_t sumuj_czekanie(const vector<int64_t> & czasy_przyjscia, int czas_piecz) { int64_t czas_konca = 0; // czas skonczenia ostatniego pieczenia int64_t suma_czek = 0; for (uint32_t ii=0; ii<czasy_przyjscia.size(); ii++) { int64_t zapas_czasu = czasy_przyjscia[ii] - czas_konca; if (zapas_czasu < czas_piecz) { int64_t czekanie = czas_piecz - zapas_czasu; suma_czek += czekanie; czas_konca = czasy_przyjscia[ii] + czekanie; } else czas_konca = czasy_przyjscia[ii]; // czekanie = 0 } return suma_czek; } pair<int64_t,int64_t> suma_czekania_i_skok(const vector<int64_t> & czasy_przyjscia, int czas_piecz) { int64_t czas_konca = 0; // czas skonczenia ostatniego pieczenia int64_t suma_czek = 0; int64_t skok = 0; int licznik = 0; // liczy numer klienta od ostatniego nie czekajacego for (uint32_t ii=0; ii<czasy_przyjscia.size(); ii++) { int64_t zapas_czasu = czasy_przyjscia[ii] - czas_konca; if (zapas_czasu < czas_piecz) { int64_t czekanie = czas_piecz - zapas_czasu; suma_czek += czekanie; czas_konca = czasy_przyjscia[ii] + czekanie; licznik++; skok += licznik; } else // czekanie = 0 { czas_konca = czasy_przyjscia[ii]; licznik = 0; } } return make_pair(suma_czek, skok); } /////////////////////////////////////////// int main() { ios_base::sync_with_stdio(0); cin.tie(0); // wczytanie danych int ile_klientow, ile_piekar; cin>>ile_klientow; cin>>ile_piekar; vector<int64_t> czasy_przyjscia = wczytaj_dane<int64_t>(ile_klientow); vector<piekarnik> czasy_pieczenia = wczytaj_piek(ile_piekar); // // obliczenie sumy czekania // for (auto iter = czasy_pieczenia.begin(); iter != czasy_pieczenia.end(); ++iter) // { // int64_t suma_czekania = sumuj_czekanie(czasy_przyjscia, *iter); // cout<<suma_czekania <<endl; // } // utworzenie zbioru wartosci czasu pieczenia dla ktorych nowy klient zaczyna czekac set<int64_t> zmiany; zmiany.insert(czasy_przyjscia[0]+1); for (auto iter = next(czasy_przyjscia.begin()); iter != czasy_przyjscia.end(); ++iter) { int64_t war1 = *iter - *prev(iter); // odleglosc od poprzedniego klienta int64_t war2 = *iter / (iter - czasy_przyjscia.begin() + 1); // czas na zapiekanke przy nieprzerwanym pieczeniu int64_t pocz_czekania = 1 + min(war1, war2); zmiany.insert(pocz_czekania); } // sortowanie czasow pieczenia - rosnaco sort(czasy_pieczenia.begin(), czasy_pieczenia.end(), piekarnik::cmp_czas); //zliczanie sum czekania int64_t suma_dla_ost_zmiany = 0; int64_t skok = 0; int64_t ost_zmiana = 0; set<int64_t>::iterator it_zmia = zmiany.begin(); vector<piekarnik>::iterator it_piek = czasy_pieczenia.begin(); while (it_piek != czasy_pieczenia.end()) { while (it_piek != czasy_pieczenia.end() && (it_zmia == zmiany.end() || it_piek->czas_piecz < *it_zmia)) { int64_t suma_dla_piek = suma_dla_ost_zmiany + skok *(it_piek->czas_piecz - ost_zmiana); it_piek->suma_czekania = suma_dla_piek; ++it_piek; } while (it_piek != czasy_pieczenia.end() && it_zmia != zmiany.end() && it_piek->czas_piecz >= *it_zmia) // pomijanie pustych przedzialow { ++it_zmia; } // nowe wartosci sumy dla zmiany, skoku itp ost_zmiana = *(prev(it_zmia)); tie(suma_dla_ost_zmiany, skok) = suma_czekania_i_skok(czasy_przyjscia, ost_zmiana); } sort(czasy_pieczenia.begin(), czasy_pieczenia.end(), piekarnik::cmp_index); for (auto it = czasy_pieczenia.begin(); it!= czasy_pieczenia.end(); ++it) { cout<<it->suma_czekania <<endl; } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 | #include <iostream> #include <vector> #include <algorithm> #include <stdint.h> #include <set> #include <tuple> using namespace std; struct piekarnik { public: int index; int czas_piecz; int64_t suma_czekania; piekarnik(){} piekarnik (int czas, int ind) : index(ind), czas_piecz(czas), suma_czekania(0){} static bool cmp_index (const piekarnik & a, const piekarnik & b) {return a.index < b.index;} static bool cmp_czas (const piekarnik & a, const piekarnik & b) {return a.czas_piecz < b.czas_piecz;} }; template <class T> vector<T> wczytaj_dane(int ile) { vector<T> dane(ile, 0); for (int ii=0; ii<ile; ii++) { T dana_ii; cin>>dana_ii; dane[ii] = dana_ii; } return dane; } vector<piekarnik> wczytaj_piek(int ile) { vector<piekarnik> piek(ile); for (int ii=0; ii<ile; ii++) { int dana_ii; cin>>dana_ii; piek[ii] = piekarnik(dana_ii, ii); } return piek; } bool cmp_greater (const int i, const int j) { return (i>j); } int64_t sumuj_czekanie(const vector<int64_t> & czasy_przyjscia, int czas_piecz) { int64_t czas_konca = 0; // czas skonczenia ostatniego pieczenia int64_t suma_czek = 0; for (uint32_t ii=0; ii<czasy_przyjscia.size(); ii++) { int64_t zapas_czasu = czasy_przyjscia[ii] - czas_konca; if (zapas_czasu < czas_piecz) { int64_t czekanie = czas_piecz - zapas_czasu; suma_czek += czekanie; czas_konca = czasy_przyjscia[ii] + czekanie; } else czas_konca = czasy_przyjscia[ii]; // czekanie = 0 } return suma_czek; } pair<int64_t,int64_t> suma_czekania_i_skok(const vector<int64_t> & czasy_przyjscia, int czas_piecz) { int64_t czas_konca = 0; // czas skonczenia ostatniego pieczenia int64_t suma_czek = 0; int64_t skok = 0; int licznik = 0; // liczy numer klienta od ostatniego nie czekajacego for (uint32_t ii=0; ii<czasy_przyjscia.size(); ii++) { int64_t zapas_czasu = czasy_przyjscia[ii] - czas_konca; if (zapas_czasu < czas_piecz) { int64_t czekanie = czas_piecz - zapas_czasu; suma_czek += czekanie; czas_konca = czasy_przyjscia[ii] + czekanie; licznik++; skok += licznik; } else // czekanie = 0 { czas_konca = czasy_przyjscia[ii]; licznik = 0; } } return make_pair(suma_czek, skok); } /////////////////////////////////////////// int main() { ios_base::sync_with_stdio(0); cin.tie(0); // wczytanie danych int ile_klientow, ile_piekar; cin>>ile_klientow; cin>>ile_piekar; vector<int64_t> czasy_przyjscia = wczytaj_dane<int64_t>(ile_klientow); vector<piekarnik> czasy_pieczenia = wczytaj_piek(ile_piekar); // // obliczenie sumy czekania // for (auto iter = czasy_pieczenia.begin(); iter != czasy_pieczenia.end(); ++iter) // { // int64_t suma_czekania = sumuj_czekanie(czasy_przyjscia, *iter); // cout<<suma_czekania <<endl; // } // utworzenie zbioru wartosci czasu pieczenia dla ktorych nowy klient zaczyna czekac set<int64_t> zmiany; zmiany.insert(czasy_przyjscia[0]+1); for (auto iter = next(czasy_przyjscia.begin()); iter != czasy_przyjscia.end(); ++iter) { int64_t war1 = *iter - *prev(iter); // odleglosc od poprzedniego klienta int64_t war2 = *iter / (iter - czasy_przyjscia.begin() + 1); // czas na zapiekanke przy nieprzerwanym pieczeniu int64_t pocz_czekania = 1 + min(war1, war2); zmiany.insert(pocz_czekania); } // sortowanie czasow pieczenia - rosnaco sort(czasy_pieczenia.begin(), czasy_pieczenia.end(), piekarnik::cmp_czas); //zliczanie sum czekania int64_t suma_dla_ost_zmiany = 0; int64_t skok = 0; int64_t ost_zmiana = 0; set<int64_t>::iterator it_zmia = zmiany.begin(); vector<piekarnik>::iterator it_piek = czasy_pieczenia.begin(); while (it_piek != czasy_pieczenia.end()) { while (it_piek != czasy_pieczenia.end() && (it_zmia == zmiany.end() || it_piek->czas_piecz < *it_zmia)) { int64_t suma_dla_piek = suma_dla_ost_zmiany + skok *(it_piek->czas_piecz - ost_zmiana); it_piek->suma_czekania = suma_dla_piek; ++it_piek; } while (it_piek != czasy_pieczenia.end() && it_zmia != zmiany.end() && it_piek->czas_piecz >= *it_zmia) // pomijanie pustych przedzialow { ++it_zmia; } // nowe wartosci sumy dla zmiany, skoku itp ost_zmiana = *(prev(it_zmia)); tie(suma_dla_ost_zmiany, skok) = suma_czekania_i_skok(czasy_przyjscia, ost_zmiana); } sort(czasy_pieczenia.begin(), czasy_pieczenia.end(), piekarnik::cmp_index); for (auto it = czasy_pieczenia.begin(); it!= czasy_pieczenia.end(); ++it) { cout<<it->suma_czekania <<endl; } return 0; } |