Submission #185515

#	Time	Username	Problem	Language	Result	Execution time	Memory
185515		FieryPhoenix	Robots (IOI13_robots)	C++11	90 / 100	3067 ms	32404 KiB

robots

#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

vector<pair<int,int>>v;
bool taken[1000001];

bool check(int A, int B, int T, int X[], int Y[], int W[], int S[], int t){
  for (int i=0;i<T;i++)
    taken[i]=false;
  int ind=0;
  set<pair<int,int>>st; //-W, index
  for (int j=0;j<=(int)v.size();j++){
    while (ind<B && (j==(int)v.size() || v[j].first>=Y[ind])){
      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].second,j});
  }
  vector<int>vW;
  for (int i=0;i<T;i++)
    if (!taken[i])
      vW.push_back(v[i].second);
  sort(vW.begin(),vW.end());
  int avai=0;
  ind=0;
  for (int j=0;j<=(int)vW.size();j++){
    while (ind<A && (j==(int)vW.size() || vW[j]>=X[ind])){
      avai-=min(t,avai);
      ind++;
    }
    if (j==(int)vW.size())
      break;
    avai++;
  }
  if (avai==0)
    return true;
  else
    return false;
}
	  
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
  if (T>=700000)
    assert(0);
  sort(X,X+A);
  sort(Y,Y+B);
  for (int i=0;i<T;i++)
    v.push_back({S[i],W[i]});
  sort(v.begin(),v.end());
  int MAX=501;
  int low=0,high=MAX,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==MAX)
    return -1;
  else
    return high;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 0 / 10