Submission #535466

#	Time	Username	Problem	Language	Result	Execution time	Memory
535466		kebine	Robots (IOI13_robots)	C++17	76 / 100	3059 ms	25312 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
 
int putaway(int a, int b, int T, int x[], int y[], int W[], int S[]){
  vector<pair<int,int>> w, s;
  for(int i=0;i<T;i++) w.push_back({W[i], i});
  for(int i=0;i<T;i++) s.push_back({S[i], i});
  sort(w.begin(),w.end(), [&](pair<int,int> _x, pair<int,int> _y){
    return S[_x.second] > S[_y.second];
  });
  sort(s.begin(),s.end(), [&](pair<int,int> _x, pair<int,int> _y){
    return W[_x.second] > W[_y.second];
  });
  sort(x, x + a);
  sort(y, y + b);
  queue<pair<int,int>> q;
  vector<int> dist(T, -1);
  for(int i=0;i<a;i++)
  {
    for(int j=0;j<T;j++)
      if(w[j].first < x[i] && dist[w[j].second] == -1)
      {
        q.push({x[i], w[j].second});
        dist[w[j].second] = 1;
        break;
      }
  }
  for(int i=0;i<b;i++)
  {
    for(int j=0;j<T;j++)
    {
      if(s[j].first < y[i] && dist[s[j].second] == -1)
      {
        q.push({-y[i], s[j].second});
        dist[s[j].second] = 1;
        break;
      }
    }
  }
  while(!q.empty()){
    int c = q.front().first, id = q.front().second;// capacity & type, current vertex
    q.pop();
    if(c < 0) // size robot
    {
      c = -c;
      for(int i=0;i<T;i++)
      {  
        if(dist[s[i].second] == -1 && s[i].first < c)
        {
          dist[s[i].second] = dist[id] + 1;
          // cout << "S, C : " << c << ' ' << id << "-> " << s[i].second << "\n";
          q.push({-c, s[i].second});
          break;
        }
      }
    }
    else // weight robot
    {
      for(int i=0;i<T;i++)
      {
        if(dist[w[i].second] == -1 && w[i].first < c)
        {
          dist[w[i].second] = dist[id] + 1;
          // cout << "W , C : " << c << " " << id << "-> " << w[i].second << "\n";
          q.push({c, w[i].second});
          break;
        }
      }
    }
  }
  // for(int i=0;i<T;i++) cout << dist[i] << " "; cout << '\n';
  if(*min_element(dist.begin(), dist.end()) == -1) return -1;
  else return *max_element(dist.begin(), dist.end());
}
 
// int main(){
//   cin.tie(0) -> ios_base::sync_with_stdio(0);
 
//   int a, b, t;
//   cin >> a >> b >> t;
//   int x[a], y[b], w[t], s[t];
//   for(int i=0;i<a;i++) cin >> x[i];
//   for(int i=0;i<b;i++) cin >> y[i];
//   for(int i=0;i<t;i++)
//   {
//     cin >> w[i] >> s[i];
//   }
//   cout << putaway(a, b, t, x, y, w, s);
 
// }

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