Codeforces Round #593 DIV2 D問題 - Alice and the Doll

Source

Codeforces Round #593 DIV2 D問題 (1750pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20191027-1）のコード

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

//no-unlocked
int N, M, K, X, Y;
set<int> OX[1d5], OY[1d5];

void eraseX(int x){
  for(int y : OX[x]) OY[y].erase(x);
  OX[x].clear();
}

void eraseY(int y){
  for(int x : OY[y]) OX[x].erase(y);
  OY[y].clear();
}

{
  int x1, x2, y1, y2, d;
  ll walk = 0, all;
  rd(N,M,K);
  rep(K){
    rd(X--,Y--);
    OX[X].insert(Y);
    OY[Y].insert(X);
  }
  all = (ll) N * M - K;

  d = 0;
  x1 = 0; x2 = N-1;
  y1 = 0; y2 = M-1;

  for(;;){
    if(x1 > x2 || y1 > y2) break;

    if(d==0 && OY[y2].size()==x2-x1+1) eraseY(y2), y2--, continue;
    if(d==1 && OX[x2].size()==y2-y1+1) eraseX(x2), x2--, continue;
    if(d==2 && OY[y1].size()==x2-x1+1) eraseY(y1), y1++, continue;
    if(d==3 && OX[x1].size()==y2-y1+1) eraseX(x1), x1++, continue;

    if(d==0 && OX[x1].size()==0) d=(d+1)%4, x1++, walk += y2-y1+1, continue;
    if(d==1 && OY[y2].size()==0) d=(d+1)%4, y2--, walk += x2-x1+1, continue;
    if(d==2 && OX[x2].size()==0) d=(d+1)%4, x2--, walk += y2-y1+1, continue;
    if(d==3 && OY[y1].size()==0) d=(d+1)%4, y1++, walk += x2-x1+1, continue;

    if(d==0) walk += getFirst(OX[x1]) - y1;
    if(d==1) walk += getFirst(OY[y2]) - x1;
    if(d==2) walk += y2 - getLast(OX[x2]);
    if(d==3) walk += x2 - getLast(OY[y1]);
    break;
  }
  wt(if[walk==all, "Yes", "No"]);
}

Current time: 2024年04月20日03時40分53秒
Last modified: 2019年11月02日03時42分06秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF593 CF_Div2_D
トップページに戻る

Logged in as: unknown user (not login)