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
| #include <bits/stdc++.h>
#pragma optimization_level 3 #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #pragma GCC optimization ("unroll-loops")
#define MAX_N 22 #define INF 987654321 #define EPS 1e-9 #define ll long long #define pll pair<ll, ll> #define vpll vector<pll> #define vall3 vector<array<ll,3>> #define all3 array<ll,3> #define all5 array<ll,5> #define vall5 vector<all5> #define vll vector<ll> #define vs vector<string> #define usll unordered_set<ll> #define vvs vector<vs> #define vvll vector<vll> #define all(a) begin(a), end(a)
using namespace std;
vll solve(ll l, vpll ants) { vpll pos, dis; ll n = ants.size(), left = 0, right = n - 1; vll res; for(ll i = 0; i < n; i++) { pos.push_back({ants[i].first, i}); dis.push_back({ ants[i].second ? l - ants[i].first : ants[i].first, i}); } sort(all(pos)); sort(all(dis)); for(ll i = 0, m; i < n; i++) { m = i; vll tmp; while(m < n and dis[i].first == dis[m].first) { auto d = ants[dis[m++].second].second; if(d) tmp.push_back(pos[right--].second); else tmp.push_back(pos[left++].second); } sort(all(tmp)); i = m - 1; for(auto& id : tmp) res.push_back(id + 1); }
return res; }
int main() { ios_base::sync_with_stdio(0); cin.tie(0); ll tc; cin >> tc; for (ll i = 1; i <= tc; i++) { ll n, l, d, p; vpll ants; cin >> n >> l; for (ll i = 0; i < n; i++) { cin >> p >> d; ants.push_back({p, d}); } auto res = solve(l, ants); cout << "Case #" << i << ": "; for (auto r : res)cout << r << ' '; cout << endl; }
return 0; }
|