結果

問題 No.1 道のショートカット
ユーザー motimoti
提出日時 2016-06-21 22:25:45
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 4,766 bytes
コンパイル時間 1,160 ms
コンパイル使用メモリ 117,792 KB
実行使用メモリ 814,948 KB
最終ジャッジ日時 2023-09-22 12:43:46
合計ジャッジ時間 6,075 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 MLE -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int solver::main()’:
main.cpp:189:39: warning: iteration 11 invokes undefined behavior [-Waggressive-loop-optimizations]
     rep(i, 11) rep(j, 66) color[i][j] = -1;
                           ~~~~~~~~~~~~^~~~
main.cpp:25:33: note: within this loop
 #define REP(i,a,b) for(int i=a;i<(int)b;i++)
                                 ^
main.cpp:26:18: note: in expansion of macro ‘REP’
 #define rep(i,n) REP(i,0,n)
                  ^~~
main.cpp:189:16: note: in expansion of macro ‘rep’
     rep(i, 11) rep(j, 66) color[i][j] = -1;
                ^~~

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <assert.h>
#include <array>
#include <cstdio>
#include <cstring>
#include <random>
#include <functional>
#include <numeric>
#include <bitset>
#include <fstream>

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { cout << #a << " = " << a << endl; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }

typedef long long ll;
int const inf = 1<<29;

int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
template<class T> constexpr bool in_range(T y, T x, T H, T W) { return 0<=y&&y<H&&0<=x&&x<W; }

namespace solver {
int H, W;
int K;
vector<string> G;
int color[66][11];

bool equals_(double a, double b) { return abs(a - b) < 1e-10; }

struct Data {
  double y, x; int w;
  Data(double y, double x, int w) : y(y), x(x), w(w) {}
};

bool operator == (const Data& a, const Data& b) { return equals_(a.y, b.y) && equals_(b.x, b.x) && a.w == b.w; }

void coloring(int y, int x, vector<vector<bool>>& vis) {
  color[y][x] = K;
  rep(k, 4) {
    int ny = y + dy[k], nx = x + dx[k];
    if(!in_range(ny, nx, H, W)) continue;
    if(G[ny][nx] != G[y][x]) continue;
    if(vis[ny][nx]) continue;
    vis[ny][nx] = 1;
    coloring(ny, nx, vis);
  }
}

auto InvalidData = Data(0,0,-inf);

vector<int> getChildrenNum(int pcnum) {
  vector<int> ret;
  rep(i, H) rep(j, W) {
    if(color[i][j] == -1) continue;
    if(!in_range(i + 1, j, H, W)) continue;
    if(color[i][j] != pcnum && color[i + 1][j] == pcnum)
      ret.push_back(color[i][j]);
  }
  sort(ret.begin(), ret.end());
  ret.erase(unique(ret.begin(), ret.end()), ret.end());
  return ret;
}

Data getBlockData(int cnum) {
  int num = 0;
  double y = 0, x = 0;
  rep(i, H) rep(j, W) {
    if(color[i][j] == cnum) {
      num ++;
      y += i + 0.5;
      x += j + 0.5;
    }
  }

  y /= num;
  x /= num;

//  cout << "block data: " << cnum << endl; watch(y); watch(x); watch(num);
  return Data(y, x, num);
}

pair<int, int> getBlockHeadX(int col) {
  int xL = 1000, xR = -1;
  rep(i, H) rep(j, W) {
    if(color[i][j] != -1 && color[i][j] != col && in_range(i+1, j, H, W) && color[i+1][j] == col) {
      minimize(xL, j);
      maximize(xR, j+1);
    }
  }
//  watch(xL) watch(xR)
  return make_pair(xL, xR);
}

bool safeY(double cy, int cnum) {
  bool safe = 0;
  rep(i, H) rep(j, W) {
    if(color[i][j] == cnum) {
      safe |= cy < i;
    }
  }
//  watch(safe)
  return safe;
}

//template<class T> ostream& operator << (ostream& ost, vector<T> const& v) { ost << "["; rep(i, v.size()) { if(i) ost << ", "; ost << v[i]; } ost << "]"; return ost; }

Data rec(int cnum) {

  auto vc = getChildrenNum(cnum);
//  watch(cnum); cout << vc << endl;

  double y = 0, x = 0; int w = 0;
  for(auto && u: vc) {
    auto e = rec(u);
    if(e == InvalidData) return InvalidData;
    y += e.y * e.w;
    x += e.x * e.w;
    w += e.w;
  }

  if(w > 0) {
    double cy = y / w, cx = x / w;
    auto xlxr = getBlockHeadX(cnum);
    if(!safeY(cy, cnum)) return InvalidData; // topが高いほうが下
    if(cx <= xlxr.first || xlxr.second <= cx) return InvalidData;
  }

  auto mydata = getBlockData(cnum);
  y += mydata.y * mydata.w;
  x += mydata.x * mydata.w;
  w += mydata.w;

  y /= w;
  x /= w;

  return Data(y, x, w);
}

bool solve() {
  int bottomc = -1;
  int xl = -1, xr = -1;
  rep(j, W) {
    if(color[H-1][j] != -1) {
      bottomc = color[H-1][j];
      xl = j;
      break;
    }
  }

  for(int j=W-1; j>=0; j--) {
    if(color[H-1][j] != -1) {
      xr = j+1;
      break;
    }
  }

  auto d = rec(bottomc);
  if(d == InvalidData) return false;

//  cout << "my sweet angel ayasetan" << endl; watch(xl); watch(xr); cout << "d.x = " << d.x << endl;

  return xl < d.x && d.x < xr;
}

int main() {

  while(cin >> W >> H && (W|H)) {
    G.clear(); G.resize(H);
    rep(i, H) cin >> G[i];
    rep(i, 11) rep(j, 66) color[i][j] = -1;

    K = 0;
    vector<vector<bool>> vis(H, vector<bool>(W));
    rep(i, H) rep(j, W) {
      if(G[i][j] == '.') continue;
      if(vis[i][j]) continue;
      vis[i][j] = 1;
      coloring(i, j, vis);
      K++;
    }

//    rep(i, H) rep(j, W) {   printf("%2d", color[i][j]);    if(j == W-1) cout << endl;   }

    cout << (solve() ? "STABLE" : "UNSTABLE") << endl;
  }
  
  return 0;
}
}

int main() {
  return solver::main();
}
0