Codeforces Round #693 (Div. 3) DETANOJA...

システス落ちしなければA,B,C,Dの4完でレートは上がりそう！
Eも時間内に通したかったけど無限にバグらせてしまった……。

A. Cards for Friends

を何回2で割れるか数えて、その数えたがより大きければYES。

B. Fair Division

重さ1の飴も重さ2の飴も偶数個あったらYES。重さ1の飴が0個以上かつ偶数個以上あって、重さ2の飴が奇数個の場合もYES。それ以外はNO。

C. Long Jumps

前からdpで通る。最初にとしてから、のとき、でたぶんいけるはず……（ガチャガチャしてたらプレテストが通った）

D. Even-Odd Game

降順にソートして前から順にAlice→Bob→Alice……と取っていくのがお互いにとって最適ぽい？何でそうなるのか分からないけどとりあえず反例が思いつかなかったので投げたら通る（完）

E. Correct Placement

オンオン……。向きはどっちでもいいのでとして、indexを持っておいてHで昇順ソートして前から順番に見る。今見ているものよりHが小さいもののWとindexはmapに、Hが同じものはstackに入れておく。1つ前よりHが大きくなったらstackの中身は全部mapに移す。mapの中で一番Wが小さいもののindexが答えになる。

実装

#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int MOD = 1000000007;
const int INF = 1000000000000000;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

signed main(){
  int T;
  cin >> T;

  rep(t, T){
    int N;
    cin >> N;
    //{h, w, id}
    vector<pair<pair<int, int>, int>> A(N);
    rep(i, N){
      int H, W;
      cin >> H >> W;
      if( H > W ) swap(H, W);
      A[i] = make_pair(make_pair(H, W), i);
    }
    sort(A.begin(), A.end());

    vector<int> ans(N, -1);

    //mpの中は常に今見ているものよりhが小さい
    map<int, int> mp;
    stack<pair<int, int>> st;
    for( int i = 0; i < N; i++ ){
      int H = A[i].first.first;
      int W = A[i].first.second;
      int now = A[i].second;

      //前の数字とHが同じだったら
      if( i == 0 || H == A[i-1].first.first ){
        st.push({W, now});
        for( auto p : mp ){
          int sw = p.first;
          if( sw < W ){
            ans[now] = p.second+1;
            break;
          }
        }
      }else{
        while( !st.empty() ){
          int sw = st.top().first;
          int id = st.top().second;
          mp[sw] = id;
          st.pop();
        }
        for( auto p : mp ){
          if( p.first < W ) ans[now] = p.second+1;
          break;
        }
        st.push({W, now});
      }
    }

    rep(i, N) cout << ans[i] << " ";
    cout << "\n";
  }

}

強くなりたいナーーー　ポヤシミ……