Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "iostream"
- #include "vector"
- #include "algorithm"
- #include "utility"
- #include "cstdio"
- #include "functional"
- #include "set"
- #include "algorithm"
- #include <cassert>
- #include <ctime>
- using namespace std;
- vector<int> konduktorzy;
- typedef long long int lli;
- lli sprawdzono_przedzialow (long long int t)
- {//ile przedzialow sprawdzono lub zaczęto sprawdzać w chwili t
- if (t<0) return 0;
- lli licznik=0;
- for (vector<int>::iterator konduktor =konduktorzy.begin();konduktor!=konduktorzy.end();++konduktor )
- {
- licznik += (t+(*konduktor))/(*konduktor); //
- }
- return licznik;
- };
- lli przybliz_czas_double(lli przedzialow, int sup)
- {
- double predkosc=0;
- przedzialow-=konduktorzy.size()*(1-sup);//
- for (vector<int>::iterator konduktor = konduktorzy.begin(); konduktor != konduktorzy.end(); ++konduktor )
- {
- predkosc+=1.0/(*konduktor);
- }
- return (lli)((przedzialow)/predkosc)-1+sup;
- }
- lli binarne(lli przedzialow)
- {
- //lli bb= przybliz_czas(przedzialow,1);
- //lli aa= przybliz_czas(przedzialow,0);
- lli b= przybliz_czas_double(przedzialow,1);
- lli a= przybliz_czas_double(przedzialow,0);
- while (sprawdzono_przedzialow(b) < przedzialow )
- {
- b=b+(b-a);
- a=b-1;
- //printf("a jednak!");
- }
- while ( sprawdzono_przedzialow(a) >= przedzialow )
- {
- a=a-(b-a);
- if (a<0)a=-1;
- //printf("koniec swiata!");
- }
- while (a<b-1)
- {// F(a)<przedzialow<=F(b)
- lli c=(a+b+1)/2;
- lli dzial = sprawdzono_przedzialow(c);
- if (dzial<przedzialow) a=c; else b=c;
- }
- return b;
- }
- int main()
- {
- lli przedzialow;
- int k;
- scanf("%lld %d",&przedzialow,&k);
- konduktorzy.resize(k); //czasy konduktorow
- for (int i=0;i<k;i++)
- scanf("%d",&konduktorzy[i]);
- lli t_koniec = binarne(przedzialow);
- lli sprawdzono = sprawdzono_przedzialow(t_koniec);
- int zakres_czasu = (*max_element(konduktorzy.begin(),konduktorzy.end()))+1;
- vector <pair<int,int> > sprawdzenia; //sprawdzenie w czasie t konduktora k.
- sprawdzenia.reserve(k);
- for (int kon=0;kon<k;kon++)
- {
- //n log n dzieki magii liczb harmonicznych;)
- for (int hopek= (int)(konduktorzy[kon]*((t_koniec)/konduktorzy[kon]) -t_koniec ); hopek >= -zakres_czasu; hopek-= konduktorzy[kon])
- {
- sprawdzenia.push_back(make_pair(hopek,kon) );
- }
- }
- sort(sprawdzenia.begin(),sprawdzenia.end(),greater<pair<int,int> >());
- vector<lli> wyniki(k,-1);
- int ind=0;
- while (sprawdzono>przedzialow )
- {
- sprawdzono--;
- ind++;
- }
- for(;ind<sprawdzenia.size();ind++)
- {
- int kond=sprawdzenia[ind].second;
- if (wyniki[kond]<0) wyniki[kond]=sprawdzono;
- sprawdzono--;
- }
- for(int i=0;i<k;i++)
- {
- printf("%lld ", wyniki[i]);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement