Submission #1320898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320898		yeyso2	Obstacles for a Llama (IOI25_obstacles)	C++20	0 / 100	2150 ms	1499680 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> temp;
vector<int> hum;
int rows;
int cols;


vector<set<int>> bad;
set<int> good;
void initialize(std::vector<int> T, std::vector<int> H) {
  temp = T;
  hum = H;
  rows = T.size();
  cols = H.size();
  bad.resize(T.size());
  for(int i = 0; i < H.size(); i ++){
    for(int j = 0; j < T.size(); j ++){
      if(H[i] >= T[j]){
        bad[j].insert(i);
      }
    }
    if(H[i] < T[1]) good.insert(i);
  }
}
struct Coord {
  int i;
  int j;

  vector<Coord> get_adj(){
    vector<Coord> res;
    if(i > 0) res.push_back({i-1, j});
    if(j > 0) res.push_back({i, j-1});
    if(i < rows - 1) res.push_back({i+1, j});
    if(j < cols - 1) res.push_back({i, j+1});
    return res;
  }

  bool operator==(const Coord& other) const {
    return (i==other.i) && (j==other.j);
  }
};

struct Hash {
  size_t operator()(const Coord& c) const {
    size_t h1 = hash<int>{}(c.i);
    size_t h2 = hash<int>{}(c.j);
    return h1 ^ (h2 << 1);
  }
};
// Return index of closest obstacle
int look_left(int x, set<int> se){
  auto it = se.lower_bound(x - 1);
  if(it == se.begin()) return -1;
  return *it;
}
int look_right(int x, set<int> se){
  auto it = se.lower_bound(x);
  if(it == se.end()) return INT_MAX / 2;
  return *it;
}
bool can_reach(int L, int R, int S, int D) {

  if(S > D) swap(S, D);

  // Check if we can go through the top row
  int block_right = look_right(S, bad[0]);
  int block_left = look_left(D, bad[0]);
  if(block_right > D) return true;

  // Have to go down
  int open_left = look_left(block_right, good);
  if(open_left == -1) return false;
  int right = look_right(open_left, bad[2]);

  int open_right = look_right(block_left, good);
  if(open_right > R) return false;
  int left = look_left(open_right, bad[2]);

  if(left < right) return true;
  
  // Check if we can go down
  //int row0_left
  //if(T[1] > H[S] &&)
  return false;

  /*queue<Coord> q;
  q.push({0, S});
  unordered_map<Coord, bool, Hash> visited;
  Coord cur;
  while(!q.empty()){
    cur = q.front();
    q.pop();
    if(temp[cur.i] <= hum[cur.j]) continue;

    if(!visited[cur]){
      visited[cur] = true;
      //cout << cur.i << " " << cur.j << "\n";
      vector<Coord> adj = cur.get_adj();
      for(const Coord& nxt : adj){
        q.push(nxt);
      }
    }
  }
  if(visited[{0, D}]){
    return true;
  }
  return false;*/
}
/*
g++ -std=gnu++20 -Wall -O2 -pipe -static -g -o obstacles grader2.cpp obstacles.cpp

1 5
5
1 1 1 6 1
2
0 3 0 4
0 3 0 2


3 4
2 1 3
0 1 2 0
1
0 3 1 3
*/

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 21
• Subtask 5: 0 / 25
• Subtask 6: 0 / 17