Cod sursa(job #2018448)

Utilizator GoogalAbabei Daniel Googal Data 4 septembrie 2017 21:58:29
Problema Arbori de intervale Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include <algorithm>
#include <iostream>
#include <cassert>
#include <fstream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

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

const int NMAX = 30000;
const int DIM = 1000000;

struct Data {
  int val;
  int ind;
};

int n, b, pos;
int s, c;
int d[1 + NMAX];
Data a[1 + NMAX];
char str[20];
string sol;
char buff[DIM];

int read(){
  int no = 0;
  while(!isdigit(buff[pos])){
    if(++pos == DIM){
      in.read(buff, DIM);
      pos = 0;
    }
  }

  while(isdigit(buff[pos])){
    no = (no * 10) + (buff[pos] - '0');
    if(++pos == DIM){
      in.read(buff, DIM);
      pos = 0;
    }
  }

  return no;
}

void write() {
  for(int i = n; i >= 1; i--) {
    d[a[i].ind] = a[i].val;
    if(0 < s) {
      s--;
      d[a[i].ind]++;
    }
  }

  for(int i = 1; i <= n ; i++) {
    out << d[i] << ' ';
  }
}

bool cmpg(Data a, Data b) {
  return a.val > b.val;
}

bool cmpl(Data a, Data b) {
  return a.val < b.val;
}

void solve(int sgn) {
  int i = 1;
  while(i <= n && 0 < s) {
    double l = ceil(1.0L * s / (1.0L * (n - i + 1)));
    int pret1 = sgn * (d[i - 1] - a[i].val);
    int pret2 = (int)(l);
    int diff = min(pret1, pret2) * sgn;
    a[i].val += diff;
    d[i] = a[i].val;
    s -= diff * sgn;
    if(d[i] == d[i - 1] && i != 1) {
      d[i] += -1 * sgn;
      a[i].val += -1 * sgn;
      s++;
    }
    i++;
  }
}

int main()
{
  //in >> n >> b >> c;
  n = read();
  b = read();
  c = read();
  for(int i = 1; i <= n; i++) {
    //in >> a[i].val;
    a[i].val = read();
    a[i].ind = i;
    s += a[i].val;
  }

  s = c - s;
  if(s == 0) {
    write();
  } else if(s > 0) {
    sort(a + 1, a + n + 1, cmpg);
    d[0] = b;
    solve(1);
    write();
  } else {
    s *= -1;
    sort(a + 1, a + n + 1, cmpl);
    d[0] = 1;
    solve(-1);
    write();
  }

  in.close();
  out.close();
  return 0;
}