Submission #126376

#TimeUsernameProblemLanguageResultExecution timeMemory
126376nxteruRobots (IOI13_robots)C++14
76 / 100
316 ms20212 KiB
#include "robots.h" #include <bits/stdc++.h> using namespace std; typedef pair<int,int> P; #define F first #define S second #define PB push_back int n,m,q,x[50005],y[50005],par[50005],res[50005],s[50005],u[50005]; P g[1000005]; vector<int>cmx,cmy; int find(int a){ if(par[a]==a)return a; return par[a]=find(par[a]); } void unit(int a,int b){ par[a]=find(b); } bool check(int t){ for(int i=0;i<=cmy.size();i++)par[i]=i,res[i]=0; for(int i=0;i<m;i++)res[y[i]]+=t; for(int i=0;i<=cmx.size();i++)s[i]=0,u[i]=0; for(int i=0;i<n;i++)u[x[i]]+=t; for(int i=0;i<q;i++){ int p=g[i].S; p=find(p); if(p==cmy.size())s[g[i].F]++; else{ res[p]--; if(res[p]==0)unit(p,p+1); } } for(int j=cmx.size();j>=0;j--){ u[j]+=u[j+1]; s[j]+=s[j+1]; if(s[j]>u[j])return false; } return true; } int putaway(int A, int B, int T, int X[], int Y[], int W[], int R[]) { n=A,m=B,q=T; for(int i=0;i<n;i++)x[i]=X[i]-1,cmx.PB(x[i]); for(int i=0;i<m;i++)y[i]=Y[i]-1,cmy.PB(y[i]); sort(cmx.begin(),cmx.end()); sort(cmy.begin(),cmy.end()); cmx.erase(unique(cmx.begin(),cmx.end()),cmx.end()); cmy.erase(unique(cmy.begin(),cmy.end()),cmy.end()); for(int i=0;i<n;i++)x[i]=lower_bound(cmx.begin(),cmx.end(),x[i])-cmx.begin(); for(int i=0;i<m;i++)y[i]=lower_bound(cmy.begin(),cmy.end(),y[i])-cmy.begin(); for(int i=0;i<q;i++){ W[i]=lower_bound(cmx.begin(),cmx.end(),W[i])-cmx.begin(); R[i]=lower_bound(cmy.begin(),cmy.end(),R[i])-cmy.begin(); g[i]=P(W[i],R[i]); } sort(g,g+q,greater<P>()); int l=0,r=T+1; while(r-l>1){ int o=(l+r)/2; if(check(o))r=o; else l=o; } if(r>T)r=-1; return r; }

Compilation message (stderr)

robots.cpp: In function 'bool check(int)':
robots.cpp:19:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<=cmy.size();i++)par[i]=i,res[i]=0;
              ~^~~~~~~~~~~~
robots.cpp:21:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<=cmx.size();i++)s[i]=0,u[i]=0;
              ~^~~~~~~~~~~~
robots.cpp:26:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(p==cmy.size())s[g[i].F]++;
      ~^~~~~~~~~~~~
#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...