Submission #1213183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213183		vyaduct	Furniture (JOI20_furniture)	C++20	0 / 100	1 ms	320 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
 
void setIo(string in="", string out=""){
  if (!in.empty() && !out.empty()){
    freopen(in.c_str(), "r", stdin);
    freopen(out.c_str(), "w", stdout);
  }
  ios::sync_with_stdio(false);
  cin.tie(0);
}
 
#define all(c) (c).begin(), (c).end()
#define sz(c)  (int)(c).size()
#define vt     vector
#define pb     emplace_back
#define F      first
#define S      second
#define pll    pair<ll,ll>
#define MP     make_pair

int first_true(int lo, int hi, function<bool(int)> f) {
  hi++;
  while (lo < hi) {
    int mid = lo + (hi - lo)/2;
    if (f(mid)) hi = mid; 
    else  lo = mid + 1;
  }
  return lo;
}

class Bazooka {
public:
  vt<int> row, rw; // For top path
  vt<int> col, cl; // For bottom pat
  int n,m;

  void build(int N, int M){
    n = N, m = M;
    row.assign(n, 0); rw.assign(n, 0);
    col.assign(m, 0); cl.assign(m, 0);
  }

  void insert(int x, int y){ // O(M*N) on amortization
    rw[x]=m-y;
    if (y == m-1 || x == 0 ? 1 : abs((m-y) - row[x-1]) <= 1){
      int r = first_true(0, n-1, [&](int i){return row[i] < m-y;});
      for (int i=r;i<=x;i++) row[i]=m-y;
      int xx=x;
      while(xx+1<n && row[xx]-rw[xx+1]<=1 && rw[xx+1]!=row[xx+1]){
        xx++;
        row[xx]=rw[xx];
      }
    }

    cl[y]=n-x;
    if (x == n-1 || y == 0 ? 1 : abs((n-x)-col[y-1]) <= 1){
      int c = first_true(0, m-1, [&](int j){return col[j] < n-x;});
      for (int j=c;j<=y;j++) col[j]=n-x;
      while(y+1<m && col[y] - cl[y+1] <= 1 && cl[y+1] != col[y+1]){
        col[y]=cl[y];
        y++;
      }
    }
  }

  bool iscritical(int x, int y){ // (x,y) =! (0,0) && (x,y) != (n-1,m-1)
    bool up = (x>0?(m-row[x-1]<=y && m-row[x]>y):y<m-row[x]);
    bool right = m-row[x]==y+1;
    bool corner_ur = (x>0&&y>0?m-row[x-1]==y+1:0);
    bool top = up || right || corner_ur;
    // cout << up << " " << right << " " <<  corner_ur << endl;

    bool down = (x<n-1?n-col[y]==x+1:y<m-row[x]);
    bool left = (y==0 && m-row[x]>y) || (y > 0 && n-col[y-1] <= x);
    bool corner_dl = (y>0?n-col[y-1]==x+1:0);
    bool bottom = down || left || corner_dl;
    // cout << down << " " << left << " " << corner_dl << endl;
    return top && bottom;
  }
};

void solve(){
  int n,m; cin>>n>>m;
  Bazooka john;
  john.build(n, m);
  vt<vt<int>> C(n, vt<int>(m, 0));
  for (int i=0;i<n;i++){
    for (int j=0;j<m;j++){
      int c; cin>>c;
      C[i][j]=c;
      if (c) john.insert(i,j);
    }
  }

  int q; cin>>q;
  int i=1;
  while(q--){
    int x,y; cin>>x>>y; x--,y--;
    C[x][y]=1;
    if (john.iscritical(x, y)){
      cout << 0 << endl;
    } else {
      cout << 1 << endl;
      john.insert(x, y);
    }
    i++;
    // cout << "row[] = "; for (int i=0;i<n;i++) cout << john.row[i] << " "; cout << endl;
    // cout << "col[] = "; for (int i=0;i<m;i++) cout << john.col[i] << " "; cout << endl;
  }
}

int main(){
  setIo();
  int tt=1;
  // cin>>tt;
  while(tt--) solve();
  return 0;
}

Compilation message (stderr)

furniture.cpp: In function 'void setIo(std::string, std::string)':
furniture.cpp:8:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     freopen(in.c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
furniture.cpp:9:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     freopen(out.c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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