제출 #589446

#제출 시각아이디문제언어결과실행 시간메모리
589446ogibogi2004로봇 (IOI13_robots)C++14
14 / 100
273 ms13680 KiB
#include "robots.h" #include <bits/stdc++.h> using namespace std; const int MAXT=1e6+6; const int MAXN=5e4+6; struct toy { int w,s; bool operator<(const toy &other)const { if(w!=other.w)return w<other.w; return s>other.s; } }; vector<toy>toys; vector<int>weak,small; bool used[MAXT]; int fen[MAXT]; void update(int idx,int val) { idx++; if(idx<=0)return; for(;idx<MAXN;idx+=idx&(-idx)) { fen[idx]+=val; } } int query(int idx) { if(idx<0)return 0; idx++; int ret=0; for(;idx>0;idx-=idx&(-idx)) { ret+=fen[idx]; } return ret; } bool ok(int moves) { memset(used,0,sizeof(used)); memset(fen,0,sizeof(fen)); for(int i=0;i<small.size();i++)update(i,moves); set<pair<int,int> >sr; int op=(int)small.size(); for(int i=0;i<small.size();i++)sr.insert({small[i],moves}); for(int i=0;i<toys.size();i++) { int s=toys[i].s; /*int low1=0,high1=small.size()-1,mid1,best1=-1; while(low1<=high1) { mid1=(low1+high1)/2; if(small[mid1]>=s) { best1=mid1; low1=mid1+1; } else high1=mid1-1; } int j=best1; if(query(j)<=0) { continue; } else { if(moves==1)cout<<query(MAXN-1)<<endl; used[i]=1; update(j,-1); }*/ auto it=sr.lower_bound({s,-1}); if(it==sr.end())continue; used[i]=1; int val=(*it).first,cnt=(*it).second; //cout<<val<<" "<<cnt<<endl; sr.erase({val,cnt}); cnt--; if(cnt>0)sr.insert({val,cnt}); op--; //if(moves==1)cout<<op<<endl; } int cnt=moves,j=0; vector<int>small_taken,weak_taken; for(int i=0;i<toys.size();i++) { /*if(moves==1) { if(used[i]) { cout<<toys[i].w<<" "<<toys[i].s<<" S\n"; small_taken.push_back(toys[i].s); } else { cout<<toys[i].w<<" "<<toys[i].s<<" W\n"; weak_taken.push_back(toys[i].w); } }*/ if(used[i])continue; if(j>=weak.size())return 0; if(cnt==0&&j==weak.size()-1)return 0; if(cnt==0) { cnt=moves; j++; } if(toys[i].w>weak[j])return 0; cnt--; } /*if(moves==1) { sort(weak_taken.rbegin(),weak_taken.rend()); sort(small_taken.rbegin(),small_taken.rend()); if(weak_taken.size()>weak.size())cout<<"wtf1\n"; if(small_taken.size()>small.size())cout<<"wtf2\n"; }*/ return 1; } int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) { for(int i=0;i<T;i++) { toys.push_back({W[i],S[i]}); } sort(toys.rbegin(),toys.rend()); for(int i=0;i<A;i++)weak.push_back(X[i]-1); for(int i=0;i<B;i++)small.push_back(Y[i]-1); sort(weak.rbegin(),weak.rend()); for(int i=0;i<toys.size();i++) { int low=0,high=weak.size()-1,mid,best=-1; while(low<=high) { mid=(low+high)/2; if(weak[mid]>=toys[i].w) { best=mid; low=mid+1; } else high=mid-1; } if(best!=-1)toys[i].w=weak[best]; else toys[i].w=2000000001; } sort(toys.rbegin(),toys.rend()); sort(small.rbegin(),small.rend()); int low=1,high=T,mid,best=T+1; while(low<=high) { mid=(low+high)/2; if(ok(mid)) { best=mid; high=mid-1; } else low=mid+1; } if(best==T+1) { return -1; } return best; }

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

robots.cpp: In function 'bool ok(int)':
robots.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i=0;i<small.size();i++)update(i,moves);
      |                 ~^~~~~~~~~~~~~
robots.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=0;i<small.size();i++)sr.insert({small[i],moves});
      |                 ~^~~~~~~~~~~~~
robots.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<toy>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0;i<toys.size();i++)
      |                 ~^~~~~~~~~~~~
robots.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<toy>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int i=0;i<toys.size();i++)
      |                 ~^~~~~~~~~~~~
robots.cpp:101:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         if(j>=weak.size())return 0;
      |            ~^~~~~~~~~~~~~
robots.cpp:102:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         if(cnt==0&&j==weak.size()-1)return 0;
      |                    ~^~~~~~~~~~~~~~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:129:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<toy>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for(int i=0;i<toys.size();i++)
      |                 ~^~~~~~~~~~~~
#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...