D.Dasha and chess

题意 有666个黑棋子在一个999*999的棋盘上，你只有一个白棋子，黑棋子可以走到棋盘的任何地方，白棋可以走到九宫格内的点，你和交互器轮流下棋（每次只能操作一个棋子），白棋与任何一个黑棋在同一行/同一列就算你赢，给定一个局面，让白棋赢

由鸽巢定理 以(500,500)为中心，四个象限内一定存在一个象限的棋子 \(\leq 666 / 4\)，剩下三个象限棋子的和一定 \(\geq 666 / 4 * 3 = 500\)，走到(500,500)后沿着到棋子最少的象限的对角线反方向走，白棋需要499步走到角上，有>499个棋子，所以一定会碰到一个黑棋

不写代码了

E.Andrew and Taxi

题意：给一个有向图，边有边权，翻转一个边集使得不存在环，最小化最大边权

二分

本质是求一个拓扑序 满足如果有从后面的点到前面的点的边 那么权值<=x（x是答案)

可以发现如果原图无环且新加的边可以任意翻转 一定有一种方案满足加完边以后也无环，所以只需要看二分的位置以后的边是否有环

#include 
    
     using namespace std;vector
     
      G[100005];int ind[100005], topo[100005], cnt, tpos[100005], n, m, Ans[100005];struct edge {  int u, v, w, id;  inline bool operator < (const edge &rhs) const {    return w < rhs.w;  }} e[100005];inline bool check(int pos) {  cnt = 0; fill(ind + 1, ind + 1 + n, 0);  for (int i = 1; i <= n; ++i) G[i].clear();  for (edge *it = e + pos; it < e + m; ++it) G[it->u].push_back(it->v), ++ind[it->v];  for (int i = 1; i <= n; ++i) if (!ind[i]) topo[tpos[i] = ++cnt] = i;  for (int u = 1; u <= cnt; ++u)    for (auto it = G[topo[u]].begin(); it != G[topo[u]].end(); ++it)      if (--ind[*it] == 0) topo[tpos[*it] = ++cnt] = *it;  return cnt == n;}int main() {  ios::sync_with_stdio(0);  cin.tie(0);  cin >> n >> m;  for (edge *it = e; it < e + m; ++it) cin >> it->u >> it->v >> it->w, it->id = it - e + 1;  sort(e, e + m);  int l = 0, r = m - 1, ans = m;  while (l <= r) {    int mid = l + r >> 1;    if (check(mid)) r = mid - 1, ans = mid;    else l = mid + 1;  }  check(ans);  cnt = 0;  for (int i = 0; i < ans; ++i) if (tpos[e[i].u] > tpos[e[i].v]) Ans[cnt++] = e[i].id;  cout << (ans ? e[ans - 1].w : 0) << ' ' << cnt << endl;  while (cnt--) cout << Ans[cnt] << ' ';  return 0;}