제출 #1032506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1032506		SiliconSquared	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	100 / 100	4454 ms	11876 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;
    vector<int> zz;
    bucket(){}
    void f(){
        z.resize(v.size());
        zz.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;
                zz[i]=v[i]+m;
            }else{
                z[i]=z[j+1]+1;
                zz[i]=zz[j+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;
        while (y<b && v[y].v.size()==0){y++;}
        while (y>=a && v[y].v.size()==0){y--;}
        if ((v[a].v[0]<=x) && (v[y-1].v[v[y-1].v.size()-1]>=x)){b=y;}
        else if (v[a].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(y);
    v[x].v.insert(v[x].v.begin()+v[x].find(y),y);
    v[x].f();
    x=bigfind(w[i]);
    v[x].v.erase(v[x].v.begin()+v[x].find(w[i]));
    v[x].f();
    w[i]=y;
    e++;
    if (e==B){
        bucketer();
        e=0;
    }
    // if (y==0){for (auto vv:v){for(auto vvv:vv.v){print(vvv);}print(-1);}}
    int z=0;
    x=0;
    for (int j=0;j<(int)v.size();j++){
        if (v[j].find(x)==v[j].v.size()){continue;}
        x=v[j].find(x);//print(v[j].v[x]);
        z+=v[j].z[x];//print(z);
        x=v[j].zz[x];//print(x);
    }
    return z;
}

컴파일 시 표준 에러 (stderr) 메시지

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:113:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |         if (v[j].find(x)==v[j].v.size()){continue;}
      |             ~~~~~~~~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3