Submission #36294660

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)
int read(){int r;scanf("%d",&r);return r;}
const int N=2000;

void printans(const vector<vector<int>>&ans){
  if(ans.size()) {
    assert(ans.size()==ans[0].size());
    rep(i,1,ans.size())rep(j,1,ans.size()) printf("%d%c",ans[i][j]," \n"[j+1==(int)ans.size()]);
  }
}

vector<vector<int>> solve(int n,const vector<array<int,5>>&Q,bool debug=false){
  vector<pair<int,int> > idx;
  for(auto [a,b,c,d,e]:Q)if(e) for(auto i:{a-1,b})for(auto j:{c-1,d}) if(i>0&&j>0) idx.push_back({i,j});
  sort(begin(idx),end(idx));
  idx.resize(unique(begin(idx),end(idx))-begin(idx));
  auto lb=[&](int i,int j){return lower_bound(begin(idx),end(idx),make_pair(i,j))-begin(idx);};
  if(debug)for(auto [i,j]:idx){printf("idx: %d %d\n",i,j);}
  vector<bitset<4*N+1>> matrix = {};
  for(auto [a,b,c,d,e]:Q)if(e){
    bitset<4*N+1>row;
    for(auto i:{a-1,b})for(auto j:{c-1,d})if(i>0&&j>0) row[lb(i,j)]=1;
    row[4*N]=(e==2);
    if(debug)cout<<"row:"<<row<<endl;
    matrix.push_back(row);
  }
  // 高斯消元
  vector<bool>v12(idx.size());
  {
    int i=0; // row
    rep(j,0,4*N+1){ // col
      if(i>=(int)matrix.size())break;
      rep(ii,i,matrix.size()) if(matrix[ii][j]){
        swap(matrix[i],matrix[ii]);
        break;
      }
      if(!matrix[i][j])continue;
      // matrix[i][j] == 1 // 主元
      if(debug)printf("主元 %d %d\n",i,j);
      assert(matrix[i][j]);
      if(j==4*N){
        printf("No\n");
        return {};
      }
      rep(k,0,matrix.size())if(k!=i && matrix[k][j]) matrix[k]^=matrix[i];
      i++;
    }
  }
  // printf("v12.size = %d\n",(int)v12.size());
  auto ans=vector(n+1,vector(n+1,0));
  rep(i,0,matrix.size()){
    rep(j,0,4*N+1)if(matrix[i][j]){ // 主元
      if(debug)printf("v12 主元 %d %d\n",i,j);
      auto [pi,pj]=idx[j];
      ans[pi][pj]=matrix[i][4*N];
      break;
    }
  }
  per(i,1,n+1)rep(j,1,n+1) ans[i][j]^=ans[i-1][j];
  rep(i,1,n+1)per(j,1,n+1) ans[i][j]^=ans[i][j-1];

  if(debug)printans(ans);
  // 扫描线?
  auto inc = vector(n+2,vector<array<int,3>>());
  auto pre = vector(n+2,0);
  for(auto [a,b,c,d,e]:Q)if(e){
    inc[a].push_back({c,d,1});
    inc[b+1].push_back({c,d,-1});
  }
  rep(i,1,n+1){
    for(auto [c,d,diff]:inc[i]){
      pre[c]+=diff;
      pre[d+1]-=diff;
    }
    int v=0;
    rep(j,1,n+1){
      v+=pre[j];
      if(v) ans[i][j]++; // 未填写 被覆盖
      else ans[i][j]=0;
    }
  }
  if(debug)printans(ans);
  // check 0
  auto ans0=ans;
  rep(i,1,n+1)rep(j,1,n+1)ans0[i][j]=(ans[i][j]==0)+ans0[i-1][j]+ans0[i][j-1]-ans0[i-1][j-1];
  for(auto [a,b,c,d,e]:Q)if(!e)if(ans0[b][d]-ans0[a-1][d]-ans0[b][c-1]+ans0[a-1][c-1] == 0){ // 没有0
    printf("No\n");
    return {};
  }
  printf("Yes\n");
  // if(debug)printans(ans);
  return ans;
}


void test(){
  printf("==================================\n");
  int n=3;
  auto arr=vector(n+1,vector(n+1,0));
  rep(i,1,n+1)rep(j,1,n+1) arr[i][j]=rand()%3;
  int q=3;
  vector<array<int,5>>Q;
  while(q--){
    int i0=rand()%n+1;
    int i1=rand()%n+1;
    if(i0>i1)swap(i0,i1);
    int j0=rand()%n+1;
    int j1=rand()%n+1;
    if(j0>j1)swap(j0,j1);
    int v=1;
    rep(ii,i0,i1+1)rep(jj,j0,j1+1)v*=arr[ii][jj];
    Q.push_back({i0,i1,j0,j1,v%3});
  }
  auto ans=solve(n,Q);
  if(ans.size() == 0){
    printf("============== replay ====================\n");
    printf("invalid n=%d\n",n);
    for(auto [l0,r0,l1,r1,mul]:Q) printf("%d %d %d %d %d\n",l0,r0,l1,r1,mul);
    printf("============== replay ====================\n");
    ans = solve(n,Q,true);
    assert(false);
  }
  // check
  for(auto [a,b,c,d,e]:Q){
    int v=1;
    rep(i,a,b+1)rep(j,c,d+1) v*=ans[i][j];
    if(e!=v%3){
      printf("============== replay ====================\n");
      printf("invalid n=%d\n",n);
      for(auto [l0,r0,l1,r1,mul]:Q) printf("%d %d %d %d %d\n",l0,r0,l1,r1,mul);
      printf("============== replay ====================\n");
      ans = solve(n,Q,true);
      printans(ans);
      exit(1);
      return ;
    }
  }
}


int main(){
  // rep(i,0,1000)test();
  int n=read();
  int q=read();
  vector<array<int,5>>Q;
  rep(i,0,q) Q.push_back({read(),read(),read(),read(),read()}); // 1-index 减少边界判断
  auto ans = solve(n,Q);
  printans(ans);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int read()’:
./Main.cpp:5:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    5 | int read(){int r;scanf("%d",&r);return r;}
      |                  ~~~~~^~~~~~~~~

Judge Result