Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <cstring>
- #include <algorithm>
- #include <set>
- #include <iostream>
- #include <string>
- #include <ctime>
- #include <queue>
- #include <cmath>
- #include <iomanip>
- using namespace std;
- int n,s, vmin, vmax;
- struct traffic_light {
- char red;
- char green;
- char d;
- short x;
- int tm;
- bool isRed;
- short pos;
- traffic_light() {
- recalculate();
- }
- void recalculate() {
- if (d == 0)
- d += red + green;
- isRed = d > green;
- tm = d;
- if (d - green > 0)
- tm = d - green;
- }
- void gotoNext() {
- if (isRed) {
- isRed = false;
- tm += green;
- } else {
- isRed = true;
- tm += red;
- }
- }
- double next() const {
- return (double)x / tm;
- }
- };
- struct Comp {
- bool operator () (const traffic_light &a, const traffic_light &b) const {
- double aval = a.next();
- double bval = b.next();
- if (fabs(aval - bval) < 1e-11) return a.isRed < b.isRed;
- return aval < bval;
- }
- };
- priority_queue<traffic_light, vector<traffic_light>, Comp> q;
- set<int> best;
- set<int> cur;
- int mn = 0x7f7f7f7f;
- double bestSpeed;
- traffic_light t[22222];
- void check(double speed) {
- int cross = 0;
- set<int> cur;
- for (int i=0; i<n; i++) {
- double tm = (double)t[i].x / speed;
- tm = fmod(tm, (double)t[i].red + t[i].green);
- if (fabs(tm) < 1e-13) {
- continue;
- }
- if (t[i].d <= t[i].green) {
- if (tm >= t[i].d - 1e-13 && tm <= t[i].d + t[i].red + 1e-13) {
- cross++;
- cur.insert(i+1);
- }
- } else {
- if (tm <= t[i].d - t[i].green + 1e-13) {
- ++cross;
- cur.insert(i+1);
- }
- else {
- if (tm >= t[i].d - 1e-13) {
- ++cross;
- cur.insert(i+1);
- }
- }
- }
- }
- if (cross < mn) {
- mn = cross;
- bestSpeed = speed;
- best = cur;
- }
- }
- int main(){
- freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- scanf("%d %d %d %d", &n, &s, &vmin, &vmax);
- int ans = 0;
- for (int i=0; i<n; i++ ) {
- int x, red, green, d;
- scanf("%d %d %d %d", &x, &red, &green, &d);
- traffic_light tmp;
- tmp.d = d;
- tmp.red = red;
- tmp.green = green;
- tmp.x = x;
- tmp.pos = i+1;
- tmp.recalculate();
- ans += tmp.d > tmp.green;
- if (tmp.d > tmp.green)
- cur.insert(tmp.pos);
- q.push(tmp);
- t[i] = tmp;
- }
- while (1) {
- traffic_light t = q.top();
- q.pop();
- double curSpeed = t.next();
- if (curSpeed < vmin - 1e-13) break;
- if (t.isRed) {
- --ans;
- cur.erase(t.pos);
- if (ans < mn && curSpeed <= vmax + 1e-13) {
- mn = ans;
- bestSpeed = curSpeed;
- best = cur;
- }
- } else {
- ++ans;
- cur.insert(t.pos);
- }
- t.gotoNext();
- q.push(t);
- }
- check(vmax);
- check(vmin);
- if (bestSpeed == 1e300)
- bestSpeed = vmax;
- cout << fixed << setprecision(11) << bestSpeed << endl;
- cout << best.size() << endl;
- for (set<int>::iterator it = best.begin(); it != best.end(); ++it)
- cout << *it << ' ' ;
- return 0;
- }
Add Comment
Please, Sign In to add comment