oj.uz

Submission #1046568

# Submission time Handle Problem Language Result Execution time Memory
1046568 2024-08-06T17:14:14 Z oscar1f Dancing Elephants (IOI11_elephants) C++17
50 / 100
 9000 ms 10852 KB 
#include<bits/stdc++.h>
#include "elephants.h"
using namespace std;

const int MAX_ELEPH=70*1000+5,INFINI=1000*1000*1000+5;
int nbEleph,taillePhoto;
int posTri[MAX_ELEPH];
int posCour[MAX_ELEPH];

void init(int N, int L, int X[]) {
    nbEleph=N;
    taillePhoto=L;
    for (int i=0;i<nbEleph;i++) {
        posTri[i]=X[i];
        posCour[i]=X[i];
    }
}

int calc() {
    int ans=0,dernDeb=-INFINI;
    for (int i=0;i<nbEleph;i++) {
        if (dernDeb+taillePhoto<posTri[i]) {
            ans++;
            dernDeb=posTri[i];
        }
    }
    return ans;
}

int update(int posModif, int valNouv) {
    int deb=0,fin=nbEleph-1,mid;
    while (deb!=fin) {
        mid=(deb+fin+1)/2;
        if (posTri[mid]<=posCour[posModif]) {
            deb=mid;
        }
        else {
            fin=mid-1;
        }
    }
    int pos=deb;
    posTri[pos]=valNouv;
    posCour[posModif]=valNouv;
    while (pos>0 and posTri[pos]<posTri[pos-1]) {
        swap(posTri[pos-1],posTri[pos]);
        pos--;
    }
    while (pos<nbEleph-1 and posTri[pos]>posTri[pos+1]) {
        swap(posTri[pos],posTri[pos+1]);
        pos++;
    }
    return calc();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8552 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8552 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8552 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 583 ms 10588 KB Output is correct
8 Correct 1331 ms 10696 KB Output is correct
9 Correct 1321 ms 10844 KB Output is correct
10 Correct 2262 ms 10848 KB Output is correct
11 Correct 2289 ms 10852 KB Output is correct
12 Correct 4220 ms 10848 KB Output is correct
13 Correct 2300 ms 10848 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8552 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 583 ms 10588 KB Output is correct
8 Correct 1331 ms 10696 KB Output is correct
9 Correct 1321 ms 10844 KB Output is correct
10 Correct 2262 ms 10848 KB Output is correct
11 Correct 2289 ms 10852 KB Output is correct
12 Correct 4220 ms 10848 KB Output is correct
13 Correct 2300 ms 10848 KB Output is correct
14 Correct 858 ms 10740 KB Output is correct
15 Correct 3153 ms 10764 KB Output is correct
16 Execution timed out 9046 ms 10844 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8552 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 583 ms 10588 KB Output is correct
8 Correct 1331 ms 10696 KB Output is correct
9 Correct 1321 ms 10844 KB Output is correct
10 Correct 2262 ms 10848 KB Output is correct
11 Correct 2289 ms 10852 KB Output is correct
12 Correct 4220 ms 10848 KB Output is correct
13 Correct 2300 ms 10848 KB Output is correct
14 Correct 858 ms 10740 KB Output is correct
15 Correct 3153 ms 10764 KB Output is correct
16 Execution timed out 9046 ms 10844 KB Time limit exceeded
17 Halted 0 ms 0 KB -