이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
const int DECA=(1<<17),MAX_CHEV=100*1000+5;
int nbChev,nbRound,nivNouv;
int nbGau[DECA],nbDro[DECA];
int tropFort[MAX_CHEV],debut[MAX_CHEV],nbGagn[MAX_CHEV],enCours[MAX_CHEV];
vector<int> bataille;
void modif(int pos,int coeff) {
enCours[pos]=coeff;
pos+=DECA;
while (pos>1) {
if (pos%2==0) {
nbGau[pos/2]+=coeff;
}
else {
nbDro[pos/2]+=coeff;
}
pos/=2;
}
}
void trouveInter(int pos,int nbAvant,int debInter,int finInter) {
if (pos<DECA) {
if (nbAvant>finInter or nbAvant+nbGau[pos]+nbDro[pos]<debInter) {
return;
}
trouveInter(2*pos,nbAvant,debInter,finInter);
trouveInter(2*pos+1,nbAvant+nbGau[pos],debInter,finInter);
}
else {
if (nbAvant+1>=debInter and nbAvant+1<=finInter and enCours[pos-DECA]==1) {
bataille.push_back(pos-DECA);
}
}
}
bool verif(int deb,int fin) {
return ((tropFort[fin]-tropFort[deb])==0);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
nbChev=N;
nbRound=C;
nivNouv=R;
for (int i=0;i<nbChev-1;i++) {
tropFort[i+1]=tropFort[i];
if (K[i]>nivNouv) {
tropFort[i+1]++;
}
}
for (int i=0;i<nbChev;i++) {
modif(i,1);
debut[i]=i;
}
int debInter,finInter;
for (int i=0;i<nbRound;i++) {
bataille.clear();
trouveInter(1,0,S[i]+1,E[i]+1);
/*for (int j:bataille) {
cout<<j<<" ";
}*/
debInter=debut[bataille[0]];
finInter=bataille.back();
for (int j=0;j<(int)bataille.size()-1;j++) {
modif(bataille[j],-1);
}
debut[bataille.back()]=debInter;
if (verif(debInter,finInter)) {
nbGagn[debInter]++;
nbGagn[finInter]--;
}
//cout<<debInter<<" "<<finInter<<" "<<verif(debInter,finInter)<<endl;
}
for (int i=1;i<nbChev;i++) {
nbGagn[i]+=nbGagn[i-1];
}
int rep=0,posRep=0;
for (int i=0;i<nbChev;i++) {
if (nbGagn[i]>rep) {
rep=nbGagn[i];
posRep=i;
}
}
return posRep;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |