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
| #include <algorithm> #include <cassert> #include <cmath> #include <cstdio> #include <cstring> #include <fstream> #include <iostream> #include <set> using namespace std;
typedef long long int64;
const int INF = 0x3f3f3f3f; const int MAXN = 100010;
struct frog { int a, p, id; frog* succ; frog* prev; } frogs[MAXN];
struct comp { bool operator()(const pair<int, frog*>& a, const pair<int, frog*>& b) const { return (a.first == b.first) ? (a.second->id < b.second->id) : (a.first < b.first); } }; set<pair<int, frog*>, comp> s;
#include <cctype> #include <cstdio>
template <typename T = int> inline T read() { T X = 0, w = 0; char ch = 0; while (!isdigit(ch)) { w |= ch == '-'; ch = getchar(); } while (isdigit(ch)) { X = (X << 3) + (X << 1) + (ch ^ 48); ch = getchar(); } return w ? -X : X; }
int m;
int time_to_hit(const frog& a, const frog& b) { if (a.id == b.id) return INF; int d = (b.p - a.p + m) % m; if (a.id > b.id) { d = (d + b.a) % m; } if (d <= a.a) return 1; if (a.a <= b.a) return INF; return (d - b.a - 1) / (a.a - b.a) + 1; }
int main() { int n = read(); m = read(); for (int i = 1; i <= n; i++) { frogs[i].p = read(); frogs[i].a = read(); frogs[i].id = i; } sort(frogs + 1, frogs + n + 1, [](const frog& a, const frog& b) -> bool { return a.p < b.p; }); for (int i = 1; i <= n; i++) { frogs[i].succ = &frogs[(i + 1 > n) ? 1 : (i + 1)]; frogs[i].prev = &frogs[(i - 1 < 1) ? n : (i - 1)]; } for (int i = 1; i <= n; i++) { s.insert(make_pair(time_to_hit(frogs[i], *frogs[i].succ), &frogs[i])); } while (!s.empty()) { auto cur = *s.begin(); if (cur.first == INF) break; frog* now = cur.second; s.erase(cur); s.erase(make_pair(time_to_hit(*now->prev, *now), now->prev)); s.erase( make_pair(time_to_hit(*now->succ, *now->succ->succ), now->succ)); now->p += time_to_hit(*now, *now->succ); now->a--; now->succ = now->succ->succ; now->succ->prev = now; s.insert(make_pair(time_to_hit(*now->prev, *now), now->prev)); s.insert(make_pair(time_to_hit(*now, *now->succ), now)); } cout << s.size() << endl; for (auto i : s) { cout << i.second->id << ' '; } cout << endl; return 0; }
|