Submission #1061917

#TimeUsernameProblemLanguageResultExecution timeMemory
1061917vjudge1Robots (IOI13_robots)C++17
76 / 100
715 ms46308 KiB
#include "robots.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back const int N=1000100; const int R=100000; int a,b,t; vector<int>x; vector<int>y; vector<int>w; vector<int>s; vector<pair<int,int>> WS; int itpass(int md, vector<int> tosmall){ if(b==0) return 0; sort(y.rbegin(),y.rend()); /* for(int i=0;i<tosmall.size();i++){ cout<<tosmall[i]<<" "; } cout<<" TOSMALL"<<endl; */ int pos=0; int cont=md; for(int i=0;i<tosmall.size();i++){ if(pos>=b){ return 0; } if(tosmall[i]>=y[pos]){ //cout<<y[pos]<<" POS"<<endl; return 0; } cont--; if(cont==0){ pos++; cont=md; } } return 1; } int binary(int mn, int md, int mx){ while(mx!=md){ priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>>pq; vector<int>tosmall; //cout<<mn<<" "<<md<<" "<<mx<<endl; int pos=0; int cont=md; bool posible=true; for(int i=0;i<t;i++){ //cout<<WS[i].first<<" "<<x[pos]<<" WI XPOS"<<endl; //cout<<tosmall.size()<<endl; if(pos>=a){ tosmall.pb(WS[i].second); posible=false; continue; } pq.push({WS[i].second,WS[i].first}); if(pq.top()[1]>=x[pos]){ tosmall.pb(pq.top()[0]); pq.pop(); posible=false; continue; } cont--; if(cont==0){ cont=md; pos++; } } if(posible==true){ mx=md; md=(mn+mx)/2; }else{ sort(tosmall.rbegin(),tosmall.rend()); int look=itpass(md,tosmall); if(look==1){ mx=md; md=(mn+mx)/2; }else{ mn=md; md=(mn+mx+1)/2; } } } return mx; } int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){ a=A; b=B; t=T; for(int i=0;i<t;i++){ w.pb(W[i]); s.pb(S[i]); WS.pb({w[i],s[i]}); } for(int i=0;i<a;i++){ x.pb(X[i]); } for(int i=0;i<b;i++){ y.pb(Y[i]); } sort(WS.rbegin(),WS.rend()); sort(x.rbegin(),x.rend()); int answer=binary(1,(t+3)/2,t+2); if(answer>t) return -1; return answer; }

Compilation message (stderr)

robots.cpp: In function 'int itpass(int, std::vector<int>)':
robots.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=0;i<tosmall.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...