oj.uz

Submission #1005124

# Submission time Handle Problem Language Result Execution time Memory
1005124 2024-06-22T07:34:53 Z thelepi Furniture (JOI20_furniture) C++17
5 / 100
 5000 ms 63536 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 11 ms 348 KB Output is correct
3 Correct 15 ms 564 KB Output is correct
4 Correct 15 ms 604 KB Output is correct
5 Correct 15 ms 616 KB Output is correct
6 Correct 21 ms 736 KB Output is correct
7 Correct 24 ms 1116 KB Output is correct
8 Correct 21 ms 600 KB Output is correct
9 Correct 86 ms 1108 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 11 ms 348 KB Output is correct
3 Correct 15 ms 564 KB Output is correct
4 Correct 15 ms 604 KB Output is correct
5 Correct 15 ms 616 KB Output is correct
6 Correct 21 ms 736 KB Output is correct
7 Correct 24 ms 1116 KB Output is correct
8 Correct 21 ms 600 KB Output is correct
9 Correct 86 ms 1108 KB Output is correct
10 Correct 731 ms 2392 KB Output is correct
11 Correct 27 ms 776 KB Output is correct
12 Correct 802 ms 16324 KB Output is correct
13 Correct 128 ms 5716 KB Output is correct
14 Correct 1854 ms 16060 KB Output is correct
15 Correct 1819 ms 14388 KB Output is correct
16 Correct 1706 ms 11600 KB Output is correct
17 Execution timed out 5079 ms 63536 KB Time limit exceeded
18 Halted 0 ms 0 KB -