Submission #1320851

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

obstacles

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

set<int> bad;
void initialize(std::vector<int> T, std::vector<int> H) {
  temp = T;
  hum = H;
  rows = T.size();
  cols = H.size();

  for(int i = 0; i < H.size(); i ++){
    if(H[i] > T[0]){
      bad.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);
  }
};
bool can_reach(int L, int R, int S, int D) {

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

  auto it = bad.lower_bound(S);
  if(it == bad.end()) return true;
  if(*it <= D) return false;
  return true;

  /*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
6 1 1 1 6
2
0 3 0 4
0 3 1 3


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