Submission #241543

#TimeUsernameProblemLanguageResultExecution timeMemory
241543vanicSegway (COI19_segway)C++14
40 / 100
1089 ms1144 KiB
#include <iostream> #include <math.h> #include <cstdio> #include <algorithm> #include <vector> #include <queue> using namespace std; const int maxn=2e4+5, maxs=305; int v[maxn][3]; priority_queue < pair < int, int > > pos[maxs]; //int dio[maxn]; int ispred[maxn]; int ubrz[maxn]; vector < int > ubrzavam; bool acel[maxs]; int sol[maxn]; int inv(int x){ return 1e9-x; } int main(){ /*+ for(int i=1; i<300; i++){ printf("%d ", i); } printf("\n");*/ int n; cin >> n; for(int i=0; i<n; i++){ cin >> v[i][0] >> v[i][1] >> v[i][2]; } int m; cin >> m; int a; for(int i=0; i<m; i++){ cin >> a; acel[a]=1; } for(int i=0; i<n; i++){ pos[0].push({inv(v[i][0]), i}); } int cilj=n; int mini; bool prog; int proslo=0; int mjesto; int isto; int juric=0; vector < pair < double , int > > l; pair < int, int > p; priority_queue < pair < int, int > > q; while(cilj){ if(!juric){ mini=100; for(int i=0; i<300; i++){ if(!pos[i].empty()){ mini=min(mini, inv(pos[i].top().first)); } } } else{ mini=1; } proslo+=mini; // cout << proslo << '\n'; for(int i=299; i>-1; i--){ while(!pos[i].empty()){ p=pos[i].top(); pos[i].pop(); p.first=inv(p.first); p.first-=mini; if(p.first==0 || ubrz[p.second]){ if(i+1==300){ // cout << "CILJ " << p.second << '\n';; cilj--; sol[p.second]=proslo; } else if(ubrz[p.second]){ // cout << "ubrzava " << p.second << endl; ubrz[p.second]--; p.first=v[p.second][(i+1)/100]; if(!ubrz[p.second]){ juric--; } } else{ p.first=v[p.second][(i+1)/100]; } if(!ubrz[p.second] && acel[i+1]){ ubrzavam.push_back(p.second); } pos[i+1].push({inv(p.first), p.second}); } else{ q.push({inv(p.first), p.second}); } } pos[i]=q; while(!q.empty()){ q.pop(); } } mjesto=pos[300].size(); for(int i=299; i>=0; i--){ q=pos[i]; while(!q.empty()){ l.push_back({(double)(v[q.top().second][i/100]-inv(q.top().first))/v[q.top().second][i/100], q.top().second}); q.pop(); } sort(l.begin(), l.end()); for(int j=l.size()-1; j>-1; j--){ isto=1; while(j-1>-1 && l[j].first==l[j-1].first){ ispred[l[j].second]=mjesto; j--; isto++; } ispred[l[j].second]=mjesto; mjesto+=isto; } l.clear(); } while(!ubrzavam.empty()){ ubrz[ubrzavam.back()]=ispred[ubrzavam.back()]%20; if(ubrz[ubrzavam.back()]){ juric++; } ubrzavam.pop_back(); } } for(int i=0; i<n; i++){ cout << sol[i] << '\n'; } return 0; }

Compilation message (stderr)

segway.cpp: In function 'int main()':
segway.cpp:47:7: warning: unused variable 'prog' [-Wunused-variable]
  bool prog;
       ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...