oj.uz

Submission #429860

# Submission time Handle Problem Language Result Execution time Memory
429860 2021-06-16T10:05:23 Z oscar1f Jousting tournament (IOI12_tournament) C++17
49 / 100
 1000 ms 1872 KB 
#include<bits/stdc++.h>
/*#include <stdio.h>
#include <stdlib.h>
#include <assert.h>*/

using namespace std;
/*
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
*/
const int MAX_CHEV=100*1000,DECA=(1<<17);
int record=0,posRec;
int selec[MAX_CHEV][2];
vector<pair<int,int>> posi,nouv_posi;
int arbreMax[2*DECA];
int cumu[MAX_CHEV+1];

int calc_max(int debInter,int finInter) {
  if (debInter==finInter) {
    return arbreMax[debInter];
  }
  if (debInter%2==1) {
    return max(arbreMax[debInter],calc_max(debInter+1,finInter));
  }
  if (finInter%2==0) {
    return max(arbreMax[finInter],calc_max(debInter,finInter-1));
  }
  return calc_max(debInter/2,finInter/2);
}

int GetBestPosition(int nbChev, int nbTour, int nivDern, int *niveau, int *deb, int *fin) {
  for (int i=0;i<nbChev;i++) {
    posi.push_back(make_pair(i,i));
  }
  for (int i=0;i<nbTour;i++) {
    nouv_posi.clear();
    for (int j=0;j<deb[i];j++) {
      nouv_posi.push_back(posi[j]);
    }
    selec[i][0]=posi[deb[i]].first;
    selec[i][1]=posi[fin[i]].second;
    //cout<<selec[i][0]<<" "<<selec[i][1]<<endl;
    nouv_posi.push_back(make_pair(selec[i][0],selec[i][1]));
    for (int j=fin[i]+1;j<posi.size();j++) {
      nouv_posi.push_back(posi[j]);
    }
    posi=nouv_posi;
  }
  //cout<<endl;
  for (int i=0;i<nbChev-1;i++) {
    arbreMax[DECA+i]=niveau[i];
  }
  for (int i=DECA-1;i>0;i--) {
    arbreMax[i]=max(arbreMax[2*i],arbreMax[2*i+1]);
  }
  for (int i=0;i<nbTour;i++) {
    if (nivDern>calc_max(selec[i][0]+DECA,selec[i][1]-1+DECA)) {
      //cout<<i<<endl;
      cumu[selec[i][0]]++;
      cumu[selec[i][1]+1]--;
    }
  }
  record=cumu[0];
  posRec=0;
  for (int i=1;i<nbChev;i++) {
    cumu[i]+=cumu[i-1];
    //cout<<cumu[i]<<" ";
    if (record<cumu[i]) {
      record=cumu[i];
      posRec=i;
    }
  }
  return posRec;

}




//int GetBestPosition(int N, int C, int R, int *K, int *S, int *E);
/*
int main() {
  int tmp;

  char *inbuf, *outbuf;
  inbuf = (char*) malloc(inbuf_len * sizeof(char));
  outbuf = (char*) malloc(outbuf_len * sizeof(char));
  tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
  assert(tmp == 0);
  tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);
  assert(tmp == 0);

  int N, C, R;
  int *K, *S, *E;
  tmp = scanf("%d %d %d", &N, &C, &R);
  assert(tmp == 3);
  K = (int*) malloc((N-1) * sizeof(int));
  S = (int*) malloc(C * sizeof(int));
  E = (int*) malloc(C * sizeof(int));
  int i;
  for (i = 0; i < N-1; i++) {
    tmp = scanf("%d", &K[i]);
    assert(tmp == 1);
  }
  for (i = 0; i < C; i++) {
    tmp = scanf("%d %d", &S[i], &E[i]);
    assert(tmp == 2);
  }

  printf("%d\n", GetBestPosition(N, C, R, K, S, E));

  return 0;

}*/

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:44:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int j=fin[i]+1;j<posi.size();j++) {
      |                         ~^~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 4 ms 716 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 3 ms 736 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 716 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 896 KB Output is correct
2 Correct 41 ms 1020 KB Output is correct
3 Correct 5 ms 980 KB Output is correct
4 Correct 90 ms 1012 KB Output is correct
5 Correct 33 ms 1036 KB Output is correct
6 Correct 26 ms 1016 KB Output is correct
7 Correct 36 ms 1024 KB Output is correct
8 Correct 44 ms 1008 KB Output is correct
9 Correct 2 ms 972 KB Output is correct
10 Correct 48 ms 1000 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1067 ms 1872 KB Time limit exceeded
2 Halted 0 ms 0 KB -