Submission #1005124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005124		thelepi	Furniture (JOI20_furniture)	C++17	5 / 100	5079 ms	63536 KiB

furniture

#include <iostream>
#include <bitset>
#include <cassert>
#include <map>

using namespace std;

int n, m;
bitset<1000> done[1000]{};
bitset<1000> path[1000]{};
map<pair<int, int>, bool> chdone;

void erasePath(int x, int y){
  while(x < m - 1 || y < n - 1){
    if(x < m - 1 && path[y][x + 1]){
      x++;
      path[y][x] = false;
    } else {
      assert((y < n - 1 && path[y + 1][x]));
      y++;
      path[y][x] = false;
    }
  }
}

bool findPath(int x, int y, int startx, int starty, bool erase){
  if(done[y][x] || chdone[pair<int, int>{x, y}])
    return false;
  if(x == m - 1 && y == n - 1){
    if(erase) erasePath(startx, starty);
    path[y][x] = true;
    return true;
  }
  if(x == m - 1){
    if(findPath(x, y + 1, startx, starty, erase)){
      path[y][x] = true;
      return true;
    } else {
      chdone[pair<int, int>{x, y}] = true;
      return false;
    }
  }
  if(findPath(x + 1, y, startx, starty, erase)){
    path[y][x] = true;
    return true;
  }
  if(y == n - 1){
    chdone[pair<int, int>{x, y}] = true;
    return false;
  }
  if(findPath(x, y + 1, startx, starty, erase)){
    path[y][x] = true;
    return true;
  }
  chdone[pair<int, int>{x, y}] = true;
  return false;
}

void apply(){
  for(auto it = chdone.begin(); it != chdone.end(); it++){
    done[it->first.second][it->first.first] = it->second;
  }
  chdone.clear();
}

int main(int, char**){
  cin >> n >> m;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      int c;
      cin >> c;
      done[i][j] = c == 1;
    }
  }
  findPath(0, 0, 0, 0, false);
  int q;
  cin >> q;
  
  for (int i = 0; i < q; i++)
  {
    int x, y;
    cin >> y >> x;
    x--;
    y--;
    if(!path[y][x]){
      done[y][x] = true;
      cout << "1" << "\n";
      continue;
    }
    chdone.clear();
    chdone[pair<int, int>{x, y}] = true;
    if(!findPath(0, 0, 0, 0, true)){
      cout << "0" << "\n";
      continue;
    } else{
      cout << "1" << "\n";
      apply();
    }
  }
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 95