Submission #185492

#	Time	Username	Problem	Language	Result	Execution time	Memory
185492		FieryPhoenix	Robots (IOI13_robots)	C++11	76 / 100	3026 ms	13404 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
#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());
  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 (ind>=A || j==(int)vW.size())
      break;
    avai++;
  }
  if (avai==0)
    return true;
  else
    return false;
  */
  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;
}

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