Submission #540725

#	Time	Username	Problem	Language	Result	Execution time	Memory
540725		MilosMilutinovic	Comparing Plants (IOI20_plants)	C++14	0 / 100	66 ms	4816 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> L;
vector<int> R;

void init(int k, vector<int> r) {
  int n = r.size();
  L.resize(n);
  R.resize(n);
  int high = n;
  while (*min_element(r.begin(), r.end()) != 1e9) {
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    auto Cnt = [&](int i) {  
      int ret = 0, val = r[i];
      for (int j = 0; j + 1 < k; j++) {
        i -= 1;
        if (i < 0) {
          i += n;
        }
        ret += (r[i] == val);
      }
      return ret;
    };
    sort(order.begin(), order.end(), [&](int i, int j) {
      if (r[i] != r[j]) {
        return r[i] < r[j];
      }
      return Cnt(i) > Cnt(j);
    });
    //assert(Cnt(order[0]) == 0);    
    int ptr = 0;
    while (ptr + 1 < n && r[order[ptr + 1]] == r[order[ptr]] && Cnt(order[ptr + 1]) == Cnt(order[ptr])) {
      ptr += 1;
    }            
    for (int i = 0; i <= ptr; i++) {
      L[order[i]] = high - ptr;
      R[order[i]] = high;
      r[order[i]] = 1e9;
    }
    high -= (ptr + 1);
  }
  /*for (int i = 0; i < n; i++) {
    cout << L[i] << " " << R[i] << '\n';
  }*/
}

int compare_plants(int x, int y) {
  if (L[x] > R[y]) {
    return 1;
  }
  if (R[x] < L[y]) {
    return -1;
  }
  return 0;
}

• Subtask 1: 0 / 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