Waiting for the dawn

CF 99A

daily codeforces

CF 80A

#include<iostream>


#include<algorithm>


using namespace std;


int prime[17]={-1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53},n,m;


int main(){


    cin>>n>>m;


    if(*upper_bound(prime,prime+17,m)==n || *upper_bound(prime,prime+17,m)==n) cout<<"YES";


    else cout<<"NO\n";


    return 0;


}

CF 1609D

#define int ll
int deg[MAXN];
struct edge {
  int u, v;
};
void solve() {
  int n, m, k;
  cin >> n >> m >> k;
  vector<int> a(n + 1);
  int r = 0;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    r = max(r, a[i]);
  } 
  vector<edge> E;
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    E.push_back({u, v});
  }
  function<bool(int)> check = [&] (int mid) {
    for (int i = 1; i <= n; ++i) deg[i] = 0;
    vector<vector<int>> ED(n + 1);
    for (auto& e : E) {
      if (a[e.u] <= mid && a[e.v] <= mid) {
        ED[e.u].push_back(e.v);
        deg[e.v]++;
      }
    }
    queue<int> q;
    vector<int> dp(n + 1);
    for (int i = 1; i <= n; ++i) {
      if (!deg[i]) {
        q.push(i);
        dp[i] = 1;
      }
    }
    while (!q.empty()) {
      auto u = q.front();
      q.pop();
      for (int &v : ED[u]) {
        deg[v]--;
        if (!deg[v]) {
          q.push(v);
        }
        dp[v] = max(dp[u] + 1, dp[v]);
      } 
    }
    for (int i = 1; i <= n; ++i) {
      if (deg[i]) {
        return true;
      }
    }
    return *max_element(dp.begin() + 1, dp.end()) >= k;
  };
  int l = 0, mid, ans = -1;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (check(mid)) {
      ans = mid;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  if (k == 1) {
    ans = *min_element(a.begin() + 1, a.end());
  }
  cout << ans << '\n';
  return ;
}

刚面完DB，感觉贼傻逼，一个拓扑排序没DEBUG出来，操了，这下小丑完了😅，我真吐了，不会是秋招唯一一个机会了吧。 MD

CF 300B

void solve() {
  int n, m;
  cin >> n >> m;
  DSU dsu(n + 1);
  for (int i = 1; i <= m; ++i) {
    int u, v;
    cin >> u >> v;
    dsu.merge(u, v);
  }
  vector<vector<int>> group(n + 1);
  for (int i = 1; i <= n; ++i) {
    group[dsu.f[i]].push_back(i);
  }
  vector<vector<int>> ans;
  vector<vector<int>> one_set, two_set;
  for (int i = 1; i <= n; ++i) {
    if (group[i].size() == 3) {
      ans.push_back(group[i]);
    } else if(group[i].size() == 2) {
      two_set.push_back(group[i]);
    } else if (group[i].size() == 1) {
      one_set.push_back(group[i]);
    } else if (group[i].size() > 3) {
      cout << -1 << '\n';
      return;
    }
  }
  while (!one_set.empty() && !two_set.empty()) {
    one_set.front().insert(one_set.front().begin(), two_set.front().begin(), two_set.front().end());
    two_set.erase(two_set.begin());
    ans.push_back(one_set.front()); // front gives a reference
    one_set.erase(one_set.begin());
  }
  if (two_set.size() > 0) {
    cout << -1 << '\n';
    return;
  }
  while (one_set.size() >= 3) {
    int a, b, c;
    auto f = one_set.begin();
    a = f->front(), f = one_set.erase(f);
    b = f->front(), f = one_set.erase(f);
    c = f->front(), f = one_set.erase(f);
    ans.push_back({a, b, c});
  }
  if (one_set.size()) {
    cout << -1 << '\n';
    return;
  }
  for (auto &v : ans) {
    for (auto &e : v) {
      cout << e << ' ';
    }
    cout << '\n';
  }
  return ;
}