제출 #1032506

#제출 시각아이디문제언어결과실행 시간메모리
1032506SiliconSquared코끼리 (Dancing Elephants) (IOI11_elephants)C++17
100 / 100
4454 ms11876 KiB
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;}
      |             ~~~~~~~~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...