Submission #1308986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308986		SonicML	Robots (IOI13_robots)	C++20	100 / 100	1622 ms	19024 KiB

robots

#include "robots.h"
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>

using namespace std;

int weakN, smallN, toyN;

int const NMAX = 5e4;
int weak[1 + NMAX];
int small[1 + NMAX];

int const TMAX = 1e6;
int ind[1 + TMAX];
int weight[1 + TMAX];
int volume[1 + TMAX];

bool compareWeight(int a, int b) {
  return weight[a] < weight[b];
}

bool canSolve(int timer) {
  
  int j = 1; 
  priority_queue <pair <int, int>> pq;  
  for(int i = 1;i <= weakN;i++) {
    while(weight[ind[j]] < weak[i] && j <= toyN) {
      pq.push({volume[ind[j]], ind[j]}); 
      j++;
    }
    for(int k = 1;k <= timer && !pq.empty();k++) {
      pq.pop();  
    }
  }
  while(j <= toyN) {
    pq.push({volume[ind[j]], ind[j]});
    j++;
  } 
  for(int i = smallN;i >= 1;i--) {
    for(int k = 1;k <= timer && !pq.empty();k++) {
      if(pq.top().first < small[i]) {
        pq.pop();
      }else {
        return false;
      }
    } 
  }
  if(pq.empty()) {
    return true;
  }
  return false;
}

int cautbin(int from, int to) {
  if(from == to) {
    return from;
  } else {
    int mid = (from + to) / 2; // 0 1 -> 0
    if(canSolve(mid)) {
      return cautbin(from, mid); // 0 0
    }else {
      return cautbin(mid+1, to); // 1 1 
    }
  }
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
  weakN = A; 
  smallN = B; 
  toyN = T;
  for(int i = 1;i <= weakN;i++) {
    weak[i] = X[i-1];
  }
  for(int i = 1;i <= smallN;i++) {
    small[i] = Y[i-1];
  }
  for(int i = 1;i <= toyN;i++) {
    volume[i] = S[i-1];
    weight[i] = W[i-1];
    ind[i] = i;
  } 
  sort(ind+1, ind+toyN+1, compareWeight);
  sort(weak+1, weak+weakN+1);
  sort(small+1, small+smallN+1);
  int ans = cautbin(1, toyN);
  if(canSolve(ans) == false) {
    return -1;
  } 
  return ans;
}

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