Submission #63106

#	Time	Username	Problem	Language	Result	Execution time	Memory
63106		Arturgo	Cultivation (JOI17_cultivation)	C++14	0 / 100	2051 ms	263168 KiB

cultivation

/*
Dichotomie sur la vitesse, puis :

Glouton*/
#include <iostream>
#include <vector>
#include <list>
using namespace std;

bool debug = false;

bool canBeBeaten(vector<long long> a, vector<long long> b) {
  int posG = a.size() - 1, posD = b.size() - 1;
  int nposG = a.size() - 1, nposD = b.size() - 1;

  bool change = true;
  while(change) {
    change = false;
    while(nposG != 0 && a[nposG - 1] + b[posD] <= 0) {
      nposG--;
      if(a[nposG] <= a[posG]) {
	posG = nposG;
	change = true;
      }
    }
    while(nposD != 0 && a[posG] + b[nposD - 1] <= 0) {
      nposD--;
      if(b[nposD] <= b[posD]) {
	posD = nposD;
	change = true;
      }
    }
  }

  long long somme = a[posG] + b[posD];

  int posMinG = 0;
  for(int g = 0;g < (int)a.size();g++) {
    if(a[g] < a[posMinG]) {
      posMinG = g;
    }
  }

  int posMinD = 0;
  for(int d = 0;d < (int)b.size();d++) {
    if(b[d] < b[posMinD]) {
      posMinD = d;
    }
  }

  if(posMinD != posD || posMinG != posG) return false;

  while(a.size() > posG + 1) a.pop_back();
  while(b.size() > posD + 1) b.pop_back();

  vector<long long> maxA;
  vector<long long> maxB;
  
  for(long long elem : a) {
    if(elem + b.back() > 0) {
      return false;
    }
    if(maxA.empty())
      maxA.push_back(elem);
    else
      maxA.push_back(max(elem, maxA.back()));
  }

  for(long long elem : b) {
    if(elem + a.back() > 0) {
      return false;
    }
    if(maxB.empty())
      maxB.push_back(elem);
    else
      maxB.push_back(max(elem, maxB.back()));
  }

  posG = a.size() - 1;
  posD = b.size() - 1;

  if(debug) {
    for(long long elem : a) {
      cout << elem << " ";
    }
    cout << endl;
    for(long long elem : b) {
      cout << elem << " ";
    }
    cout << endl;

    cout << posMinG << " " << posMinD << endl;
    cout << posG << " " << posD << endl;
  }
  
  while(true) {
    if(posG == 0 && posD == 0 && a[0] + b[0] <= 0)
      return true;
    for(int dec = -1;;dec--) {
      int nposG = posG + dec;
      int nposD = posD + dec;

      if(nposD >= 0 && maxA[posG] + b[nposD] <= 0) {
	posD = nposD;
	break;
      }
      if(nposG >= 0 && maxB[posD] + a[nposG] <= 0) {
	posG = nposG;
	break;
      }

      if(nposD < 0 && nposG < 0)
	return false;
    }
  }
}

int nbJoueurs, debut, temps;
vector<int> positions;

bool check(long long value) {
  vector<long long> pileA, pileB;

  for(int iJoueur = 0;iJoueur <= debut;iJoueur++) {
    pileA.push_back(positions[debut] - positions[iJoueur] - 2 * (debut - iJoueur) * value * temps);
  }

  for(int iJoueur = nbJoueurs - 1;iJoueur >= debut;iJoueur--) {
    pileB.push_back(positions[iJoueur] - positions[debut] - 2 * (iJoueur - debut) * value * temps);
  }

  return canBeBeaten(pileA, pileB);
}

int main() {
  cin >> nbJoueurs >> debut >> temps;
  debut--;

  for(int iJoueur = 0;iJoueur < nbJoueurs;iJoueur++) {
    int position;
    cin >> position;
    positions.push_back(position);
  }

  long long deb = -1, fin = 1000 * 1000 * 1000;
  while(fin - deb > 1) {
    long long mil = (deb + fin) / 2;

    if(check(mil)) {
      fin = mil;
    }
    else {
      deb = mil;
    }
  }

  cout << deb + 1 << endl;
  /*debug = true;
    cout << check(deb + 1) << endl;*/

  return 0;
}

Compilation message (stderr)

cultivation.cpp: In function 'bool canBeBeaten(std::vector<long long int>, std::vector<long long int>)':
cultivation.cpp:53:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(a.size() > posG + 1) a.pop_back();
         ~~~~~~~~~^~~~~~~~~~
cultivation.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(b.size() > posD + 1) b.pop_back();
         ~~~~~~~~~^~~~~~~~~~
cultivation.cpp:35:13: warning: unused variable 'somme' [-Wunused-variable]
   long long somme = a[posG] + b[posD];
             ^~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20