제출 #221581

#제출 시각아이디문제언어결과실행 시간메모리
221581laoriu로봇 (IOI13_robots)C++14
0 / 100
6 ms384 KiB
#include <bits/stdc++.h> #include "robots.h" using namespace std; typedef pair <int,int> pp; pp A[1000002]; int pos[1000002],nextt[1000002],C[1000002]; int check(int a,int b,int n,int X[],int Y[],int k) { for (int i=0;i<=b;i++) nextt[i]=i,C[i]=0; vector <int> P; for (int i=n-1;i>=0;i--) { int p=pos[i]; int x=p; while (C[p]==k) { p=nextt[p+1]; // cerr<<p<<endl; } if (p==b) P.push_back(A[i].first); else { assert(C[p]<k); C[p]++; if (C[p]==k) p=nextt[p+1]; } while (C[x]==k) { nextt[x]=p; x=nextt[x+1]; } } //if ((long long) P.size()>(long long)a*k) return 0; /* cout<<"cac "<<k<<endl; for (int i=0;i<P.size();i++) cout<<P[i]<<' ';cout<<endl;*/ for (int i=0;i<P.size();i+=k) if (i/k>=a||P[i]>X[i/k]) return 0; return 1; } int putaway(int a,int b,int n,int X[],int Y[],int W[],int S[]) { sort(X,X+a,greater<int>());sort(Y,Y+b); for (int i=0;i<n;i++) { A[i].first=W[i]; A[i].second=S[i]; } sort(A,A+n); for (int i=0;i<n;i++) { int d=0;int c=b-1; pos[i]=b; while (d<=c) { int mid=(d+c)/2; if (Y[mid]>=A[i].second) {pos[i]=mid;c=mid-1;} else d=mid+1; } // cout<<A[i].first<<' '<<A[i].second<<' '<<pos[i]<<endl; } int d=1;int c=n;int res=-1; while (d<=c) { int mid=(d+c)/2; if (check(a,b,n,X,Y,mid)) {res=mid;c=mid-1;} else d=mid+1; } return res; } /*int main() { freopen("robotz.inp","r",stdin); freopen("robotz.out","w",stdout); int a,b,n,X[50002],Y[50002],W[1000002],S[1000002]; cin>>a>>b>>n; for (int i=0;i<a;i++) cin>>X[i]; for (int i=0;i<b;i++) cin>>Y[i]; for (int i=0;i<n;i++) cin>>W[i]>>S[i]; cout<<putaway(a,b,n,X,Y,W,S); }*/

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

robots.cpp: In function 'int check(int, int, int, int*, int*, int)':
robots.cpp:38:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<P.size();i+=k)
                  ~^~~~~~~~~
#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...