/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 3ms 532.0 KiB
#2 Accepted 2ms 324.0 KiB
#3 Accepted 2ms 532.0 KiB
#4 Accepted 5ms 532.0 KiB
#5 Wrong Answer 2ms 320.0 KiB
#6 Accepted 3ms 532.0 KiB
#7 Wrong Answer 5ms 320.0 KiB

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 11;
const int INF = 1e9;
const int INF_DEADLINE = 1'000'000'000;

int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};

bool inb(int x,int y){ return x>=0 && x<N && y>=0 && y<N; }

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  // read 11x11 tokens (may be separated by spaces/newlines)
  vector<string> grid(N, string(N,'#'));
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      string t;
      if(!(cin >> t)) return 0;
      grid[i][j] = t[0];
    }
  }

  // 1) fire_time multi-source BFS
  vector<vector<int>> fire(N, vector<int>(N, INF));
  queue<pair<int,int>> q;
  for(int i=0;i<N;i++) for(int j=0;j<N;j++){
      if(grid[i][j]=='F'){
        fire[i][j]=0;
        q.push({i,j});
      }
    }
  while(!q.empty()){
    auto [x,y] = q.front(); q.pop();
    for(int k=0;k<4;k++){
      int nx=x+dx[k], ny=y+dy[k];
      if(!inb(nx,ny)) continue;
      if(fire[nx][ny] > fire[x][y] + 1){
        fire[nx][ny] = fire[x][y] + 1;
        q.push({nx,ny});
      }
    }
  }

  auto is_border = [&](int x,int y){
    return x==0 || y==0 || x==N-1 || y==N-1;
  };

  // helper: BFS that checks reachability from start at a given start_time T
  auto reachable_from_with_T = [&](int sx,int sy,int T)->bool{
    if(!(T < fire[sx][sy])) return false; // start cell must be safe immediately
    vector<vector<int>> dist(N, vector<int>(N, -1));
    queue<pair<int,int>> qq;
    dist[sx][sy]=0;
    qq.push({sx,sy});
    if(is_border(sx,sy)) return true; // already border and T < fire_time
    while(!qq.empty()){
      auto [x,y] = qq.front(); qq.pop();
      int d = dist[x][y];
      int curr_time = T + d;
      for(int k=0;k<4;k++){
        int nx=x+dx[k], ny=y+dy[k];
        if(!inb(nx,ny)) continue;
        if(dist[nx][ny]!=-1) continue;
        // we will arrive at nx,ny at time T + (d+1); must be strictly less than fire[nx][ny]
        if(!(T + (d+1) < fire[nx][ny])) continue;
        dist[nx][ny] = d+1;
        if(is_border(nx,ny)) return true;
        qq.push({nx,ny});
      }
    }
    return false;
  };

  // helper: compute minimal steps to border when starting at time T (assumes reachable_from_with_T is true)
  auto min_steps_from_with_T = [&](int sx,int sy,int T)->int{
    vector<vector<int>> dist(N, vector<int>(N, -1));
    queue<pair<int,int>> qq;
    dist[sx][sy]=0;
    qq.push({sx,sy});
    if(is_border(sx,sy)) return 0;
    while(!qq.empty()){
      auto [x,y] = qq.front(); qq.pop();
      int d = dist[x][y];
      for(int k=0;k<4;k++){
        int nx=x+dx[k], ny=y+dy[k];
        if(!inb(nx,ny)) continue;
        if(dist[nx][ny]!=-1) continue;
        if(!(T + (d+1) < fire[nx][ny])) continue;
        dist[nx][ny]=d+1;
        if(is_border(nx,ny)) return dist[nx][ny];
        qq.push({nx,ny});
      }
    }
    return INF; // unreachable
  };

  // helper: whether there's a path to border using only cells with infinite fire_time
  auto reachable_via_inf_only = [&](int sx,int sy)->pair<bool,int>{
    if(!(fire[sx][sy]==INF)) return {false,INF};
    vector<vector<int>> dist(N, vector<int>(N, -1));
    queue<pair<int,int>> qq;
    dist[sx][sy]=0; qq.push({sx,sy});
    if(is_border(sx,sy)) return {true,0};
    while(!qq.empty()){
      auto [x,y]=qq.front(); qq.pop();
      int d=dist[x][y];
      for(int k=0;k<4;k++){
        int nx=x+dx[k], ny=y+dy[k];
        if(!inb(nx,ny)) continue;
        if(dist[nx][ny]!=-1) continue;
        if(fire[nx][ny]!=INF) continue;
        dist[nx][ny]=d+1;
        if(is_border(nx,ny)) return {true, dist[nx][ny]};
        qq.push({nx,ny});
      }
    }
    return {false,INF};
  };

  // collect person jobs (deadline, processing time)
  vector<pair<ll,int>> jobs;

  // compute an upper bound for binary search: use maximum finite fire time (or 0) + N*N
  int maxFiniteFire = 0;
  for(int i=0;i<N;i++) for(int j=0;j<N;j++) if(fire[i][j] < INF) maxFiniteFire = max(maxFiniteFire, fire[i][j]);
  int UB = maxFiniteFire + N*N + 5; // safe upper bound

  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      if(grid[i][j] != 'P') continue;
      // check infinite-fire-free path
      auto [ok_inf, p_inf] = reachable_via_inf_only(i,j);
      if(ok_inf){
        // infinite deadline, p = minimal steps using only INF cells (already p_inf)
        jobs.push_back({INF_DEADLINE, p_inf});
        continue;
      }
      // otherwise, binary search max T in [0,UB] such that reachable_from_with_T is true
      int lo = 0, hi = UB, best = -1;
      while(lo <= hi){
        int mid = (lo + hi) / 2;
        if(reachable_from_with_T(i,j,mid)){
          best = mid;
          lo = mid + 1;
        } else hi = mid - 1;
      }
      if(best == -1) {
        // cannot rescue this person at any start time
        continue;
      }
      int p = min_steps_from_with_T(i,j,best);
      if(p >= INF) continue; // shouldn't happen
      jobs.push_back({best, p});
    }
  }

  // scheduling: maximize number of tasks with processing times p and latest-start deadlines D
  sort(jobs.begin(), jobs.end(), [](const pair<ll,int>& a, const pair<ll,int>& b){
    if(a.first != b.first) return a.first < b.first;
    return a.second < b.second;
  });

  priority_queue<int> pq;
  long long sum = 0;
  for(auto &pr : jobs){
    ll D = pr.first;
    int p = pr.second;
    sum += p;
    pq.push(p);
    if(sum > D){
      // remove largest processing time to try to meet the deadline
      int top = pq.top(); pq.pop();
      sum -= top;
    }
  }

  cout << (int)pq.size() << "\n";
  return 0;
}

Information

Submit By
Type
Submission
Problem
P1221 G. Nine-eleven
Language
C++17 (G++ 13.2.0)
Submit At
2026-01-06 18:05:20
Judged At
2026-01-06 18:05:20
Judged By
Score
5
Total Time
5ms
Peak Memory
532.0 KiB