Submission #1031644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031644		SiliconSquared	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	10 ms	7772 KiB

elephants

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==0){return 0;}
        if (b==1){
            if (v[0]>=x){
                return 0;
            }
            return 1;
        }
        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+1;
    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);
        if (x!=v[j].v.size()){
            z+=v[j].z[x];
            x=v[j].v[x]+m;
        }
    }
    e++;
    if (e==B){
        bucketer();
        e=0;
    }
    return z;
}

Compilation message (stderr)

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:102:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         if (x!=v[j].v.size()){
      |             ~^~~~~~~~~~~~~~~
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: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3