Cod sursa(job #2948380)

Utilizator TeodorLuchianovTeo Luchianov TeodorLuchianov Data 27 noiembrie 2022 17:38:50
Problema Farfurii Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream in("farfurii.in");
ofstream out("farfurii.out");

struct SegmentTree {
  vector <int> seg;

  SegmentTree(int n = 0) {
    seg.resize(4 * n);
  }

  void update(int node, int from, int to, int pos, int val) {
    if(from == to) {
      seg[node] += val;
    }else {
      int mid = (from + to) / 2;
      if(pos <= mid) {
        update(node * 2, from, mid, pos, val);
      }else {
        update(node * 2 + 1, from, mid, pos, val);
      }
      seg[node] = seg[node * 2] + seg[node * 2 + 1];
    }
  }

  int query(int node, int from, int to, int x, int y) {
    if(from == x && to == y) {
      return seg[node];
    }else {
      int mid = (from + to) / 2, ans = 0;
      if(x <= mid) {
        ans += query(node * 2, from, mid, x, min(y, mid));
      }
      if (mid < y) {
        ans += query(node * 2 + 1, mid+1, to, max(mid+1, x), y);
      }
      return ans;
    }
  }
};

int cautbin(int from, int to, int i, int n, int inv, SegmentTree seg) {
  if(from == to) {
    return from;
  }else {
    int mid = (from + to) / 2;
    if(1LL * (mid - 1 - seg.query(1, 1, n, 1, mid)) + (1LL * (n - i) * (n - i - 1)) / 2 >= inv) {
      return cautbin(from, mid, i, n, inv, seg);
    }else {
      return cautbin(mid+1, to, i, n, inv, seg);
    }
  }
}

void printPerm(int leng, int n, int add, int inv) {
  SegmentTree seg(leng);
  for(int i = 1;i <= leng;i++) {
    int perm = cautbin(1, leng, i, leng, inv, seg);
    out << perm + add << ' ';
    inv -= (perm - 1 - seg.query(1, 1, leng, 1, perm));
    seg.update(1, 1, leng, perm, 1);
  }
}

int main() {

  int n, inv;
  in >> n >> inv;
  for(int i = n;i >= 1;i--) {
    if(1LL * (n - i + 1) * (n - i) / 2 >= inv) {
      for(int j = 1;j < i;j++) {
        out << j << ' ';
      }
      printPerm(n - i + 1, n, i - 1, inv);
      return 0;
    }
  }
  return 0;
}