Submission #1179070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179070		cot7302	Comparing Plants (IOI20_plants)	C++20	5 / 100	47 ms	6472 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)

namespace {

using i64 = long long;
using namespace std;

template <class T>
using vec = vector<T>;

template <class T>
istream& operator>>(istream& is, vec<T>& X) {
  for (auto& x : X) {
    is >> x;
  }
  return is;
}

template <class T>
constexpr T infty = 0;

template <>
constexpr int infty<int> = 1'000'000'000;

template <>
constexpr i64 infty<i64> = 1'000'000'000'000'000'000;

bool posse = false;

int N;

vec<int> id_lt, id_gt;

struct Unionfind {
	vec<int> p;
	Unionfind(int N) : p(N, -1) {};

	int find(int x) {
		return p[x] < 0 ? x : (p[x] = find(p[x]));
	}

	void join(int x, int y) {
		if ((x = find(x)) == (y = find(y))) {
			return;
		}
		p[x] += exchange(p[y], x);
	}

	bool same(int x, int y) {
		return find(x) == find(y);
	}
};

}

void init(int k, std::vector<int> r) {
  if (k == 2) {
    posse = true;
  }
  N = size(r);
  id_lt.resize(N), id_gt.resize(N);
  Unionfind uf(N);
  for (int i = 0; i < N; i++) {
    int j = (i + 1) % N;
    if (r[i] == 1) {
      uf.join(i, j);
    }
  }
  for (int i = 0; i < N; i++) {
    id_lt[i] = uf.find(i);
  }
  fill(ALL(uf.p), -1);
  for (int i = 0; i < N; i++) {
    int j = (i + 1) % N;
    if (r[i] == 0) {
      uf.join(i, j);
    }
  }
  for (int i = 0; i < N; i++) {
    id_gt[i] = uf.find(i);
  }
}

int compare_plants(int x, int y) {
  if (!posse) {
	  return 0;
  }
  auto get_posse = [](int l, int x) {
    if (x < l) {
      return N + x - l;
    }
    return x - l;
  };
  if (id_lt[x] == id_lt[y]) {
    int l = id_lt[x];
    return (get_posse(l, x) < get_posse(l, y) ? -1 : 1);
  }
  else if (id_gt[x] == id_gt[y]) {
    int l = id_gt[x];
    return (get_posse(l, x) < get_posse(l, y) ? 1 : -1);
  }
  else {
    return 0;
  }
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25