제출 #185490

#제출 시각아이디문제언어결과실행 시간메모리
185490FieryPhoenix로봇 (IOI13_robots)C++11
76 / 100
3032 ms14816 KiB
#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <cstdio> #include <map> #include <queue> #include <set> #include <iomanip> #include <deque> #include <cassert> #include <ctime> #include <cstring> #include <cstdlib> #include <chrono> #include <ctime> #include <random> #include <stack> #include <unordered_set> #include <unordered_map> #include <iterator> #include <climits> #include "robots.h" using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef long long ll; typedef long double ld; #define INF 2001001001 #define MOD 1000000007 struct toy{ int w,s; toy(int a, int b){ w=a; s=b; } }; bool cmpW(toy a, toy b){ return a.w<b.w; } bool cmpS(toy a, toy b){ return a.s<b.s; } vector<toy>v; bool taken[1000001],taken2[1000001]; int TIME=3; bool check(int A, int B, int T, int X[], int Y[], int W[], int S[], int t){ v.clear(); for (int i=0;i<T;i++){ taken[i]=false; taken2[i]=false; v.push_back(toy(W[i],S[i])); } sort(v.begin(),v.end(),cmpS); int ind=0; vector<pair<int,int>>v2; set<pair<int,int>>st; //-W, index for (int j=0;j<=(int)v.size();j++){ while (ind<B && (v[j].s>=Y[ind] || j==(int)v.size())){ int left=t; while (!st.empty() && left>0){ taken[st.begin()->second]=true; st.erase(*st.begin()); left--; } ind++; } if (ind>=B || j==(int)v.size()) break; st.insert({-v[j].w,j}); } vector<int>vW; for (int i=0;i<T;i++) if (!taken[i]) vW.push_back(v[i].w); sort(vW.begin(),vW.end()); for (int i=0;i<A;i++){ int left=t; for (int j=0;j<(int)vW.size();j++){ if (vW[j]>=X[i]) break; if (taken2[j]) continue; taken2[j]=true; left--; if (left==0) break; } } for (int i=0;i<(int)vW.size();i++) if (!taken2[i]) return false; return true; } int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){ sort(X,X+A); sort(Y,Y+B); int low=0,high=T+1,mid; while (low+1<high){ mid=(low+high)/2; if (check(A,B,T,X,Y,W,S,mid)) high=mid; else low=mid; } if (high==T+1) return -1; else return high; }
#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...