Guest User

Untitled

a guest
Feb 18th, 2018
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.88 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <set>
  5. #include <iostream>
  6. #include <string>
  7. #include <ctime>
  8. #include <queue>
  9. #include <cmath>
  10. #include <iomanip>
  11. using namespace std;
  12.  
  13. int n,s, vmin, vmax;
  14.  
  15. struct traffic_light {
  16.     char red;
  17.     char green;
  18.     char d;
  19.     short x;
  20.     int tm;
  21.     bool isRed;
  22.     short pos;
  23.  
  24.     traffic_light() {
  25.         recalculate();     
  26.     }
  27.  
  28.     void recalculate() {
  29.         if (d == 0)
  30.             d += red + green;
  31.         isRed = d > green;
  32.         tm = d;
  33.         if (d - green > 0)
  34.             tm = d - green;
  35.     }
  36.  
  37.     void gotoNext() {
  38.         if (isRed) {
  39.             isRed = false;
  40.             tm += green;
  41.         } else {
  42.             isRed = true;
  43.             tm += red;
  44.         }
  45.     }
  46.  
  47.     double next() const {
  48.         return (double)x / tm;
  49.     }
  50.  
  51. };
  52.  
  53. struct Comp {
  54.     bool operator () (const traffic_light &a, const traffic_light &b) const {
  55.         double aval = a.next();
  56.         double bval = b.next();
  57.         if (fabs(aval - bval) < 1e-11) return a.isRed < b.isRed;
  58.         return aval < bval;
  59.     }
  60. };
  61.  
  62. priority_queue<traffic_light, vector<traffic_light>, Comp> q;
  63.  
  64. set<int> best;
  65. set<int> cur;
  66.  
  67. int mn = 0x7f7f7f7f;
  68. double bestSpeed;
  69.  
  70. traffic_light t[22222];
  71.  
  72.  
  73. void check(double speed) {
  74.     int cross = 0;
  75.  
  76.     set<int> cur;
  77.  
  78.     for (int i=0; i<n; i++) {
  79.         double tm = (double)t[i].x / speed;
  80.         tm = fmod(tm, (double)t[i].red + t[i].green);
  81.         if (fabs(tm) < 1e-13) {
  82.             continue;
  83.         }
  84.  
  85.         if (t[i].d <= t[i].green) {
  86.             if (tm >= t[i].d - 1e-13 && tm <= t[i].d + t[i].red + 1e-13) {
  87.                 cross++;
  88.                 cur.insert(i+1);
  89.             }
  90.         } else {
  91.             if (tm <= t[i].d - t[i].green + 1e-13) {
  92.                 ++cross;
  93.                 cur.insert(i+1);
  94.             }
  95.             else {
  96.                 if (tm >= t[i].d - 1e-13) {
  97.                     ++cross;
  98.                     cur.insert(i+1);
  99.                 }
  100.             }
  101.         }
  102.     }
  103.  
  104.     if (cross < mn) {
  105.         mn = cross;
  106.         bestSpeed = speed;
  107.         best = cur;
  108.     }
  109. }  
  110.  
  111.  
  112. int main(){
  113.     freopen("input.txt", "r", stdin);
  114.     //freopen("output.txt", "w", stdout);
  115.  
  116.     scanf("%d %d %d %d", &n, &s, &vmin, &vmax);
  117.  
  118.     int ans = 0;
  119.  
  120.     for (int i=0; i<n; i++ ) {
  121.         int x, red, green, d;
  122.         scanf("%d %d %d %d", &x, &red, &green, &d);
  123.         traffic_light tmp;
  124.         tmp.d = d;
  125.         tmp.red = red;
  126.         tmp.green = green;
  127.         tmp.x = x;
  128.         tmp.pos = i+1;
  129.         tmp.recalculate();
  130.         ans += tmp.d > tmp.green;
  131.         if (tmp.d > tmp.green)
  132.             cur.insert(tmp.pos);
  133.         q.push(tmp);
  134.         t[i] = tmp;
  135.     }
  136.  
  137.     while (1) {
  138.         traffic_light t = q.top();
  139.         q.pop();
  140.         double curSpeed = t.next();
  141.         if (curSpeed < vmin - 1e-13) break;
  142.         if (t.isRed) {
  143.             --ans;
  144.             cur.erase(t.pos);
  145.             if (ans < mn && curSpeed <= vmax + 1e-13) {
  146.                 mn = ans;
  147.                 bestSpeed = curSpeed;
  148.                 best = cur;
  149.             }
  150.         } else {
  151.             ++ans;
  152.             cur.insert(t.pos);
  153.         }
  154.         t.gotoNext();
  155.         q.push(t);
  156.     }
  157.  
  158.     check(vmax);
  159.     check(vmin);
  160.  
  161.     if (bestSpeed == 1e300)
  162.         bestSpeed = vmax;
  163.     cout << fixed << setprecision(11) << bestSpeed << endl;
  164.     cout << best.size() << endl;
  165.     for (set<int>::iterator it = best.begin(); it != best.end(); ++it)
  166.         cout << *it << ' ' ;
  167.  
  168.     return 0;
  169. }
Add Comment
Please, Sign In to add comment