Google Code Jam 2021 Round 3 2問目 - Square Free

Source

Google Code Jam 2021 Round 3 2問目 (7pts, 13pts)
問題文

問題概要

省略

解法

省略

cLay（version 20210607-1）のコード

C++に変換後のコードはこちら

int TEST;
int X, Y, R[20], C[20], mp[20][20];
int rr[20], cc[20];
char res[20][22];
maxflow<int,int> flow;

int chk(){
  int node, st, ed, tot = 0;
  node = X + Y;
  st = node++;
  ed = node++;
  flow.init(node);

  rep(i,X) rr[i] = R[i];
  rep(i,Y) cc[i] = C[i];
  rep(i,X) rep(j,Y) if(mp[i][j]==1) rr[i]--, cc[j]--;
  rep(i,X) rep(j,Y) if(mp[i][j]==-1) flow.addEdge(i,X+j,1);

  if(min(rr(X)) < 0 || min(cc(Y)) < 0) return 0;
  if(sum(rr(X)) != sum(cc(Y))) return 0;
  tot = sum(rr(X));
  rep(i,X) if(rr[i]) flow.addEdge(st, i, rr[i]);
  rep(i,Y) if(cc[i]) flow.addEdge(X+i, ed, cc[i]);
  if(flow.solve(st,ed) == tot) return 1;
  return 0;
}

{
  flow.malloc(1d5);
  REP(TEST, rd_int()){
    wtF("Case #{TEST+1}: ");
    rd(X,Y,R(X),C(Y));
    rep(i,X) rep(j,Y) mp[i][j] = -1;

    if(!chk()) wt("IMPOSSIBLE"), continue;

    rep(i,X) rrep(j,Y){
      mp[i][j] = 1;
      if(!chk()) mp[i][j] = 0;
    }

    rep(i,X) rep(j,Y) res[i][j] = if[mp[i][j], '/', '\\'];
    rep(i,X) res[i][Y] = '\0';
    wt("POSSIBLE");
    wtLn(res(X));
  }
}

Current time: 2024年04月19日13時05分41秒
Last modified: 2021年06月07日22時54分03秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Google_Code_Jam GCJ_2021 GCJ_2021_Round_3
トップページに戻る

Logged in as: unknown user (not login)