結果

問題 No.1 道のショートカット
コンテスト
ユーザー moti
提出日時 2016-06-21 22:25:45
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
RE  
実行時間 -
コード長 4,766 bytes
コンパイル時間 1,221 ms
コンパイル使用メモリ 122,596 KB
実行使用メモリ 814,336 KB
最終ジャッジ日時 2024-07-08 04:27:45
合計ジャッジ時間 5,848 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 2 MLE * 1 -- * 1
other RE * 1 -- * 39
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int solver::main()’:
main.cpp:189:39: warning: iteration 11 invokes undefined behavior [-Waggressive-loop-optimizations]
  189 |     rep(i, 11) rep(j, 66) color[i][j] = -1;
      |                           ~~~~~~~~~~~~^~~~
main.cpp:25:33: note: within this loop
   25 | #define REP(i,a,b) for(int i=a;i<(int)b;i++)
      |                                 ^
main.cpp:26:18: note: in expansion of macro ‘REP’
   26 | #define rep(i,n) REP(i,0,n)
      |                  ^~~
main.cpp:189:16: note: in expansion of macro ‘rep’
  189 |     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