답안 #63112 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
63112	2018-07-31T18:37:42 Z	Arturgo	Sparklers (JOI17_sparklers)	C++14	100 / 100	200 ms	29004 KB

sparklers

/*
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

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

Subtask #1
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	2 ms	608 KB	Output is correct
4	Correct	2 ms	608 KB	Output is correct
5	Correct	3 ms	608 KB	Output is correct
6	Correct	2 ms	608 KB	Output is correct
7	Correct	2 ms	608 KB	Output is correct
8	Correct	2 ms	608 KB	Output is correct
9	Correct	4 ms	608 KB	Output is correct
10	Correct	2 ms	608 KB	Output is correct
11	Correct	4 ms	608 KB	Output is correct
12	Correct	3 ms	608 KB	Output is correct
13	Correct	3 ms	608 KB	Output is correct
14	Correct	3 ms	628 KB	Output is correct
15	Correct	3 ms	652 KB	Output is correct
16	Correct	4 ms	652 KB	Output is correct
17	Correct	2 ms	652 KB	Output is correct
18	Correct	4 ms	652 KB	Output is correct
19	Correct	4 ms	652 KB	Output is correct
20	Correct	4 ms	696 KB	Output is correct
21	Correct	5 ms	696 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	2 ms	608 KB	Output is correct
4	Correct	2 ms	608 KB	Output is correct
5	Correct	3 ms	608 KB	Output is correct
6	Correct	2 ms	608 KB	Output is correct
7	Correct	2 ms	608 KB	Output is correct
8	Correct	2 ms	608 KB	Output is correct
9	Correct	4 ms	608 KB	Output is correct
10	Correct	2 ms	608 KB	Output is correct
11	Correct	4 ms	608 KB	Output is correct
12	Correct	3 ms	608 KB	Output is correct
13	Correct	3 ms	608 KB	Output is correct
14	Correct	3 ms	628 KB	Output is correct
15	Correct	3 ms	652 KB	Output is correct
16	Correct	4 ms	652 KB	Output is correct
17	Correct	2 ms	652 KB	Output is correct
18	Correct	4 ms	652 KB	Output is correct
19	Correct	4 ms	652 KB	Output is correct
20	Correct	4 ms	696 KB	Output is correct
21	Correct	5 ms	696 KB	Output is correct
22	Correct	4 ms	704 KB	Output is correct
23	Correct	3 ms	712 KB	Output is correct
24	Correct	4 ms	736 KB	Output is correct
25	Correct	4 ms	792 KB	Output is correct
26	Correct	4 ms	836 KB	Output is correct
27	Correct	5 ms	976 KB	Output is correct
28	Correct	5 ms	976 KB	Output is correct
29	Correct	5 ms	976 KB	Output is correct
30	Correct	4 ms	976 KB	Output is correct
31	Correct	4 ms	976 KB	Output is correct
32	Correct	4 ms	976 KB	Output is correct
33	Correct	5 ms	976 KB	Output is correct
34	Correct	4 ms	980 KB	Output is correct
35	Correct	5 ms	992 KB	Output is correct
36	Correct	4 ms	992 KB	Output is correct
37	Correct	3 ms	1016 KB	Output is correct
38	Correct	5 ms	1028 KB	Output is correct
39	Correct	4 ms	1040 KB	Output is correct
40	Correct	4 ms	1052 KB	Output is correct

Subtask #3
50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	2 ms	608 KB	Output is correct
4	Correct	2 ms	608 KB	Output is correct
5	Correct	3 ms	608 KB	Output is correct
6	Correct	2 ms	608 KB	Output is correct
7	Correct	2 ms	608 KB	Output is correct
8	Correct	2 ms	608 KB	Output is correct
9	Correct	4 ms	608 KB	Output is correct
10	Correct	2 ms	608 KB	Output is correct
11	Correct	4 ms	608 KB	Output is correct
12	Correct	3 ms	608 KB	Output is correct
13	Correct	3 ms	608 KB	Output is correct
14	Correct	3 ms	628 KB	Output is correct
15	Correct	3 ms	652 KB	Output is correct
16	Correct	4 ms	652 KB	Output is correct
17	Correct	2 ms	652 KB	Output is correct
18	Correct	4 ms	652 KB	Output is correct
19	Correct	4 ms	652 KB	Output is correct
20	Correct	4 ms	696 KB	Output is correct
21	Correct	5 ms	696 KB	Output is correct
22	Correct	4 ms	704 KB	Output is correct
23	Correct	3 ms	712 KB	Output is correct
24	Correct	4 ms	736 KB	Output is correct
25	Correct	4 ms	792 KB	Output is correct
26	Correct	4 ms	836 KB	Output is correct
27	Correct	5 ms	976 KB	Output is correct
28	Correct	5 ms	976 KB	Output is correct
29	Correct	5 ms	976 KB	Output is correct
30	Correct	4 ms	976 KB	Output is correct
31	Correct	4 ms	976 KB	Output is correct
32	Correct	4 ms	976 KB	Output is correct
33	Correct	5 ms	976 KB	Output is correct
34	Correct	4 ms	980 KB	Output is correct
35	Correct	5 ms	992 KB	Output is correct
36	Correct	4 ms	992 KB	Output is correct
37	Correct	3 ms	1016 KB	Output is correct
38	Correct	5 ms	1028 KB	Output is correct
39	Correct	4 ms	1040 KB	Output is correct
40	Correct	4 ms	1052 KB	Output is correct
41	Correct	109 ms	3300 KB	Output is correct
42	Correct	7 ms	3300 KB	Output is correct
43	Correct	31 ms	3300 KB	Output is correct
44	Correct	199 ms	5288 KB	Output is correct
45	Correct	147 ms	6148 KB	Output is correct
46	Correct	159 ms	7068 KB	Output is correct
47	Correct	189 ms	8024 KB	Output is correct
48	Correct	154 ms	8884 KB	Output is correct
49	Correct	169 ms	9948 KB	Output is correct
50	Correct	175 ms	10840 KB	Output is correct
51	Correct	162 ms	11896 KB	Output is correct
52	Correct	180 ms	13284 KB	Output is correct
53	Correct	144 ms	13892 KB	Output is correct
54	Correct	183 ms	15336 KB	Output is correct
55	Correct	153 ms	15980 KB	Output is correct
56	Correct	152 ms	16772 KB	Output is correct
57	Correct	149 ms	17600 KB	Output is correct
58	Correct	159 ms	18668 KB	Output is correct
59	Correct	119 ms	18780 KB	Output is correct
60	Correct	174 ms	20348 KB	Output is correct
61	Correct	200 ms	21020 KB	Output is correct
62	Correct	169 ms	21960 KB	Output is correct
63	Correct	167 ms	22936 KB	Output is correct
64	Correct	155 ms	23572 KB	Output is correct
65	Correct	156 ms	24584 KB	Output is correct
66	Correct	153 ms	25408 KB	Output is correct
67	Correct	148 ms	26380 KB	Output is correct
68	Correct	177 ms	27832 KB	Output is correct
69	Correct	181 ms	29004 KB	Output is correct

답안 #63112

Compilation message

Subtask #1 30.0 / 30.0

Subtask #2 20.0 / 20.0

Subtask #3 50.0 / 50.0

Subtask #1
30.0 / 30.0

Subtask #2
20.0 / 20.0

Subtask #3
50.0 / 50.0