oj.uz

Submission #1031624

# Submission time Handle Problem Language Result Execution time Memory
1031624 2024-07-23T02:47:32 Z SiliconSquared Dancing Elephants (IOI11_elephants) C++17
0 / 100
 1 ms 600 KB 
using namespace std;
#include "elephants.h"
#include <vector>
#include <algorithm>
#define B 400
int n,m,e;
struct bucket{
    vector<int> v;
    vector<int> z;
    int x;
    bucket(){}
    void f(){
        z.resize(v.size());
        int j=v.size()-1;//last in frame
        for (int i=v.size()-1;i>=0;i--){
            while (v[i]+m<v[j]){
                j--;
            }
            if (j==(int)v.size()-1){
                z[i]=1;
            }else{
                z[i]=z[j+1]+1;
            }
        }
    }
    int find(int x){
        int a,b,y;
        a=0;b=v.size();
        if (b<2){return 0;}
        while (a+1!=b){
            y=(a+b)/2;
            if (v[y]<x){a=y;}
            else if (v[y]>x){b=y;}
            else{break;}
        }
        if (v[y]!=x){
            if(v[a]<x){y=b;}else{y=a;}
        }
        return y;
    }
};
vector<bucket> v;
int bigfind(int x){
    int a,b,y;
    a=0;b=v.size();
    while (a+1!=b){
        y=(a+b)/2;
        if (v[y].v[0]>x){b=y;}
        else {a=y;}
    }
    return a;
}
vector<int> w;

void bucketer(){
    vector<int> t=w;
    sort(t.begin(),t.end());
    v.clear();
    int i=0;
    int k=0;
    while (i<n){
        v.push_back(bucket());
        for (int j=0;j<B;j++){
            if (i+j>=n){break;}
            v[k].v.push_back(t[i+j]);
        }
        i+=B;
        k++;
    }
    for (int i=0;i<(int)v.size();i++){
        v[i].f();
    }
}

void init(int N, int L, int X[]){
    n=N;
    m=L;
    e=0;
    w.resize(n);
    for (int i=0;i<n;i++){w[i]=X[i];}
    bucketer();
}

int update(int i, int y){
    int x=bigfind(w[i]);
    v[x].v.erase(v[x].v.begin()+v[x].find(w[i]));
    v[x].f();
    w[i]=y;
    x=bigfind(y);
    v[x].v.insert(v[x].v.begin()+v[x].find(y),y);
    v[x].f();
    int z=0;
    x=0;
    for (int j=0;j<(int)v.size();j++){
        x=v[j].find(x);
        z+=v[j].z[x];
        x=v[j].v[x]+m;
    }
    e++;
    if (e==B){
        bucketer();
        e=0;
    }
    return z;
}

Compilation message

elephants.cpp: In function 'void bucketer()':
elephants.cpp:7:8: warning: '<anonymous>.bucket::x' may be used uninitialized in this function [-Wmaybe-uninitialized]
    7 | struct bucket{
      |        ^~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -