제출 #898084

#제출 시각아이디문제언어결과실행 시간메모리
898084MuhammadSaram로봇 (IOI13_robots)C++17
90 / 100
526 ms65536 KiB
#include <bits/stdc++.h> #include "robots.h" using namespace std; const int M = 1e6, inf=2e9+1; int seg[M*4]; void modify(int p,int x,int v=1,int s=0,int e=M) { if (s+1==e) { seg[v]=x; return; } int mid=(s+e)/2,lc=v*2,rc=v*2+1; if (p<mid) modify(p,x,lc,s,mid); else modify(p,x,rc,mid,e); seg[v]=min(seg[lc],seg[rc]); } int get(int l,int r,int v=1,int s=0,int e=M) { if (e<=l or r<=s) return inf; if (l<=s and e<=r) return seg[v]; int mid=(s+e)/2,lc=v*2,rc=v*2+1; return min(get(l,r,lc,s,mid),get(l,r,rc,mid,e)); } int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]) { int mx=0,mx1=0; for (int i=0;i<a;i++) mx=max(mx,x[i]); for (int i=0;i<b;i++) mx1=max(mx1,y[i]); for (int i=0;i<t;i++) if (w[i]>=mx and s[i]>=mx1) return -1; if (b==0) { int cnt[a]={}; sort(x,x+a); for (int i=0;i<t;i++) { int it=upper_bound(x,x+a,w[i])-x; cnt[it]++; } int ans=cnt[a-1],su=cnt[a-1]; for (int i=a-2;i>=0;i--) { int oops=min(cnt[i],ans*(a-i)-su); cnt[i]-=oops; su+=oops; ans+=(cnt[i]+a-i-1)/(a-i); su+=cnt[i]; } return ans; } map<int,vector<int>> cnt; vector<int> dsz; for (int i=0;i<t;i++) { if (cnt.find(s[i])==cnt.end()) dsz.push_back(s[i]); cnt[s[i]].push_back(w[i]); } int pre[1+(int)dsz.size()]={}; sort(dsz.begin(),dsz.end()); reverse(dsz.begin(),dsz.end()); int ind=0; for (int i=0;i<dsz.size();i++) { for (int j:cnt[dsz[i]]) modify(ind++,j); pre[i+1]=pre[i]+(int)cnt[dsz[i]].size(); } sort(x,x+a); sort(y,y+b); int stt=0,e=t; while (stt+1<e) { int mid=(stt+e)/2; multiset<int> msz; for (int i=0;i<t;i++) msz.insert(s[i]); ind=0; for (int i=0;i<dsz.size();i++) for (int j:cnt[dsz[i]]) modify(ind++,j); for (int i=0;i<a;i++) { for (int j=0;j<mid;j++) { if (get(0,ind)>=x[i]) break; int st=-1,en=ind-1; while (st+1<en) { int mid1=(st+en)/2; if (get(0,mid1+1)<x[i]) en=mid1; else st=mid1; } modify(en,inf); int it=upper_bound(pre,pre+1+(int)dsz.size(),en)-pre; msz.erase(msz.find(dsz[it-1])); } } for (int i=0;i<b;i++) for (int j=0;j<mid;j++) { auto it=msz.lower_bound(y[i]); if (it!=msz.begin()) { it--; msz.erase(it); } else break; } if (msz.empty()) e=mid; else stt=mid; } return e; }

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

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:76:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for (int i=0;i<dsz.size();i++)
      |               ~^~~~~~~~~~~
robots.cpp:92:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   for (int i=0;i<dsz.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...